Введение
Вычислительная математика — область математики, изучающая методы выполнения вычислений с использованием компьютеров. В более узком смысле под вычислительной математикой понимают теорию численных (в отличие от формульных) методов решения типовых математических задач.
К типовым задачам вычислительной математики относят:
- решение систем линейных уравнений
- нахождение собственных значений и векторов матрицы
- нахождение сингулярных значений и векторов матрицы
- решение нелинейных алгебраических уравнений
- решение систем нелинейных алгебраических уравнений
- решение дифференциальных уравнений (как обыкновенных дифференциальных уравнений, так и уравнений с частными производными)
- решение систем дифференциальных уравнений
- решение интегральных уравнений
- задачи аппроксимации
- задачи интерполяции
- задачи экстраполяции
- задачи численной оптимизации
Основным отличием современных методов вычислительной математики от применения обобщенных формализованных методов является то, что при решении конкретных задач вычислительного характера человек-пользователь оперирует машинными представлениями чисел, которые имеют свои существенные особенности. Их необходимо также учитывать при решении задач.
Особую роль в вычислительной математике играют оценки точности алгоритмов и их устойчивость к машинному представлению чисел в компьютере.
Исторически численные методы возникли намного раньше появления компьютеров. Так, довольно сложные методы вычислений использовались еще в античности для изучения законов движения небесных светил.
Огромную роль в технике вычислений сыграло изобретение логарифмов. Оно позволило существенно упростить методику решения многих математических задач.
Потребности решения задач расчетного характера стимулировали появление и дальнейшее развитие методов дифференциального и интегрального исчисления. У их истоков стояли Лейбниц, Ньютон, Эйлер и их ученики.
Задачи, связанные с изучением процессов со случайным исходом (вначале - игры) привели математиков Блеза Паскаль и Пьера Ферма к построению основ теории вероятностей, которая в настоящее время широко используется для анализа случайных процессов практически во всех областях науки, техники, экономики.
Новые импульсы развитие численных методов получило с появлением компьютеров, когда появилась возможность широкого внедрения расчетных методов во все стороны жизни современного общества. Особенность данного этапа развития численных методов заключается в том, что ранее вычислитель сам интуитивно правильно выполнял многие действия, которые для компьютера приходится точно формулировать, поскольку у него нет интуиции, а он лишь выполняет вычисления, которые задает ему введенная в его память программа. Поэтому пользователь должен предвидеть не только получение конечного результата, но и выполнение промежуточных расчетов.
Постановка задачи. Понятие алгоритма. Типы алгоритмов. Способы задания и исполнение алгоритма
Виды информации, используемой в задачах. Постановка задачи
Каждая задача предполагает наличие и последующее преобразование некоторой информации. Величины, используемые при решении задачи, бывают постоянными (не изменяются в процессе решения задачи) и переменными. Значение, которое переменная величина принимает в заданный момент, называют текущим. Если переменная не получила никакого значения, то ее называют неопределенной. При записи метода решения задачи всем используемым постоянным и переменным величинам присваивают имена (идентификаторы).
По типу одиночных значений, информация может представлять собой следующие объекты:
1) целые числа, например: 1; -29; 102;
2) вещественные числа, имеющие в своей записи разделяющую запятую, например: 1,5; 2,0; 0, 01;
3) логические величины, принимающие значения ”истина” или ”ложь”, которые обозначают, соответственно, 1 и 0;
4) символьные значения (любой разрешенный символ, в том числе – цифра, которая не воспринимается как число), например: А; №; &; 5; $;
5) литерные (строковые) значения, представляющие собой слова или текст (обычно данные величины выделяют кавычками), например: ”ответ=”; ”решение задачи:”; ”А=5.2”.
Первые 4 перечисленных типа относятся к простым типам, определяющим только одиночную величину. Структурированные типы данных задают наборы, состоящие из величин одного или разных типов. Характерным видом структурированных данных являются строковые значения 5), которые состоят из отдельных символьных величин.
Наряду со строковыми при решении задач наиболее часто используемыми структурированными данными являются массивы - совокупности из одиночных величин одного типа. Одномерные (линейные) массивы представляют собой заданные перечислением наборы, для которых используется единая сквозная нумерация. Обозначения номеров элементов массива могут начинаться с 0 либо с 1. В первом случае весь массив М длины n обозначают как М [1: n ], во втором случае – как М [0:(n- 1)]. Элемент массива М с номером i обозначают как М [ i ](или М (i)).
Двумерные массивы однотипных объектов называют таблицами или матрицами. У них первое измерение задает номер строки, а второе – номер столбца, в котором находится элемент. Если нумерация элементов массива начинается с 1, то таблицу Т, имеющую n строк и m столбцов, обозначают как Т [1: n; 1: m ], Элемент таблицы, стоящий в строке с номером 4 и столбце с номером 7,обозначают в этом случае как Т [4,7] (или Т (4,7)).
Как правило, вначале каждую задачу формулируют словесно. Существенным этапом в последующем решении является ее постановка в математической форме. Она подразумевает однозначное задание некоторой исходной информации, которая необходима для решения задачи (аргументы задачи), и реальной цели (выходной информации, результата задачи), которая должна быть достигнута в итоге решения.
Обозначим множество исходных данных (аргументов) задачи через Е, а множество выходных данных (результат) - через R. В задаче требуется определить R по заданным значениям Е. Рассмотрим постановку простейших задач.
Пример 1. Дать постановку задачи по определению площади прямоугольника.
Решение. Анализ показывает, что площадь прямоугольника определяется его длиной и шириной, которые в общем случае являются вещественными числами. Обозначим их через a и b. Площадь прямоугольника - также вещественное число. Обозначим его через S. С учетом данных обозначений постановка задачи принимает следующий вид:
1. Название задачи - определение площади прямоугольника.
2. И сходная информация – два вещественных числа: длина прямоугольника a и ширина прямоугольника b.
3. Цель задачи: рассчитать площадь прямоугольника S.
Таким образом, у данной задачи: Е= { a,b }, R = { S }.
Пример 2. Дать постановку задачи определения величины и номера минимального элемента в вещественном числовом массиве.
Решение. Входными данными задачи являются: длина массива, которая является целым числом и сам массив вещественных чисел. Обозначим их, соответственно, через n и М [1: n ]. Номер искомого минимального элемента (целое число) обозначим через i_min, величину минимального элемента (вещественное число) - через М_min.
Постановка задачи:
1. Название задачи - определения величины и номера минимального элемента в вещественном числовом массиве.
2. И сходная информация – два вещественных числа:
а) длина исходного массива - целое число n,
б) массив вещественных чисел М [1: n ].
3. Цель задачи: определить величину М_min (вещественное число) и номер i_min (целое число) минимального элемента в заданном массиве.
Е = { n, М [1: n ]}, R = { М_min, i_min }.
Вопросы для проверки знаний.
1. Какие типы величин используются при решении задач?
2. В чем отличие простых типов данных от структурированных? Назовите примеры данных обоих типов.
3. Назовите основные составляющие математической постановки задачи.
Практические задания.
1. Дать словесную формулировку задачи расчета периметра треугольника, заданного в декартовой системе координатами его вершин А (хА, уА), В (хВ, уВ), С (хС, уС).
2. Дать словесную формулировку задачи расчета площади треугольника, заданного длинами его сторон а, b, c.
3. Дать словесную формулировку задачи определения суммы элементов линейного числового массива М [1: n ].
Понятие алгоритма. Словесное задание алгоритмов
Понятие алгоритма первично. Словесно алгоритм можно определить как последовательность точно сформулированных и однозначно определенных действий по решению поставленной задачи. Данные основные свойства алгоритмов обеспечивают практическую возможность их выполнения (и, соответственно, решения задач) при помощи вычислительных машин. Исторически термин «алгоритм» произошло от имени великого среднеазиатского ученого 8–9 вв. Аль-Хорезми как его перевод на латинский язык (Хорезм – область современного Узбекистана).
Свойства алгоритма.
1. Понятность и однозначность. Все действия алгоритма должны быть понятны его исполнителю и допускать единственное толкование.
2. Детерминированность. Для одинаковых входных данных алгоритма выдает строго определенные одинаковые выходные данные.
3. Массовость применения. Алгоритм предназначен для решения целого класса однотипных задач. Например, для сложения двух целых чисел вариантов таких пар - бесконечное множество.
4. Результативность. Алгоритм выдаёт уникальный и предполагаемый результат для заданных входных данных.
