Решение, получаемое численным методом, обычно
 Скачать 1.35 Mb.
|
|
Тема 1 Математическая модель представляет собой формализованное описание на языке математики исследуемого явления. Таким формализованным описанием может быть система линейных, нелинейных или дифференциальных уравнений, система неравенств, определенный интеграл, полином с неизвестными коэффициентами и т. д. Математическая модель должна передавать важнейшие характеристики исследуемого объекта и отражать связи между ними. Методы решения задач Для решения задач в математике существуют следующие методы: графические, аналитические, численные. Используя графические методы, в ряде случаев можно оценить порядок искомой величины, например найти с определенной точностью корни алгебраического уравнения. Графический метод основан на геометрической интерпретации задачи. Аналитические методы позволяют найти решение задачи с помощью формулы или ряда формул. Однако на практике не всегда можно найти решение задачи с использованием аналитических методов. Подобный метод применяется, если для получения результата требуется довольно ограниченное количество вычислений, если известен диапазон, в котором справедливо решение. В качестве примеров аналитических методов можно назвать метод Гаусса, метод Крамера для систем линейных алгебраических уравнений. Численные методы – это основной инструмент решения сложных математических задач. Решение, получаемое численным методом, обычно является приближенным, т.е. содержит некоторую погрешность (ошибку). Численное решение задачи не может быть выполнено абсолютно точно, поскольку в процессе действий над числами могут возникать и накапливаться ошибки вычислений, связанные с конечной точностью представления чисел в вычислительном устройстве или накапливающиеся в результате выполнения последовательности арифметических операций. К численным методам относятся такие методы, как метод трапеций, прямоугольников, метод простых итераций. Погрешность вычислений. Погрешность вычислений Оценка точности результатов вычислений является важнейшим этапом организации вычисления. Это особенно важно при отсутствии опытных данных для сравнения. Источниками погрешности при использовании численных методов являются: 1. Математическая модель. Погрешность математической модели связана с ее приближенным описанием реального объекта. 2. Исходные данные. Исходные данные, как правило, содержат погрешности, так как они либо неточно измерены, либо являются результатом решения некоторых вспомогательных задач. 3. Метод вычислений. Применяемые для решения задачи методы, как правило, являются приближенными. Например, заменяют интеграл суммой, функцию – многочленом, производную – разностью и т. д. Погрешность метода необходимо определять для конкретного метода. Обычно ее можно оценить и проконтролировать. 4. Округление в вычислениях. Погрешность округления возникает из-за того, что вычисления производятся с конечным числом значащих цифр (для ЭВМ это 10-12 знаков). Округление производят по следующему правилу: если в старшем из отбрасываемых разрядов стоит цифра меньше пяти, то содержимое сохраняемых разрядов не изменяется; в противном случае в младший сохраняемый разряд добавляется единица с тем же знаком, что и у самого числа. Различают абсолютную и относительную погрешности. Абсолютной погрешностью ∆х некоторой величины называют разность между истинным значением x и приближенным значением х' этой величины:  Относительная погрешность  – это отношение абсолютной погрешности к модулю приближенного значения х' :  При сложении и вычитании складываются абсолютные погрешности, а при делении и умножении – относительные погрешности. Критерии численного метода Поскольку погрешность исходных данных и погрешность математической модели считаются неустранимыми и при решении задачи не учитываются, то нам необходимо иметь представление об их влиянии на точность результатов. Решение задачи считается устойчивым по исходным данным, если при малых изменениях исходных данных решение меняется несущественно. Малые погрешности в исходной величине приводят к малым погрешностям в результатах вычислений. Отсутствие устойчивости означает, что даже незначительные погрешности в исходных данных приводят к большим погрешностям или к неверному результату. Задача считается поставленной корректно , если выполнены следующие три условия: 1. Решение существует при любых допустимых исходных данных. 2. Решение является единственным. 3. Решение устойчиво по исходным данным. Если хотя бы одно из этих условий не выполняется, задача считается некорректной. При анализе вычислительного процесса одним из важнейших критериев является сходимость численного метода, которая обозначает близость полученного решения к истинному:  Другой подход к понятию сходимости используется в методах дискретизации, которые заключаются в замене задачи с непрерывными параметрами на задачу, в которой значения функции вычисляются в фиксированных точках. Это, в частности, относится к численному интегрированию и к решению дифференциальных уравнений. В этом случае под сходимостью метода понимается стремление решения дискретной задачи к решению исходной задачи при стремлении к нулю параметра дискретизации (например, шага интегрирования). Исходя из трех вышеописанных понятий для получения решения задачи с необходимой точностью ее постановка должна быть корректной, а используемый численный метод должен обладать устойчивостью и сходимостью. Вычислительные методы Под вычислительными методами обычно понимаются методы, которые используются в вычислительной математике для преобразования задач к виду, удобному для реализации на компьютере. Вычислительные методы делятся на прямые (точные) и итерационные. Метод решения задачи называется прямым , если он позволяет получить решение после выполнения конечного числа элементарных операций. В качестве элементарной операции может быть, например, вычисление интеграла, решение системы уравнений, вычисление значений функции и т. д. Важно то, что ее сложность существенно меньше, чем сложность основной задачи. Иногда прямые методы называют точными, имея в виду, что при отсутствии ошибок в исходных данных и при выполнении элементарных операций результат будет точным. Однако, при реализации метода на компьютере неизбежны ошибки округления и, следовательно, наличие вычислительной погрешности. К точным методам относятся метод Гаусса, метод квадратного корня, правило Крамера и т. д. Метод решения задачи называется итерационным , если смысл метода заключается в построении последовательных приближений к решению задачи. Вначале выбирают одно или несколько начальных приближений, а затем последовательно, используя найденные ранее приближения и однотипную процедуру расчета, строят новые приближения. Отдельный шаг итерационного процесса называется итерацией. В результате такого итерационного процесса можно теоретически построить бесконечную последовательность приближений к решению. Поэтому необходимо выбрать критерий окончания итерационного процесса. Критерий окончания связан с требуемой точностью вычислений, а именно: вычисления заканчиваются, когда погрешность приближения не превышает заданной величины. Если последовательность приближений к решению сходится (что бывает не всегда), то говорят, что итерационный метод сходится. К итерационным методам относятся метод простой итерации, метод Зейделя, метод последовательной релаксации. Решение уравнений Пусть дана некоторая функция f(x) и требуется найти все или некоторые значения X, для которых (1.1)  Корень, или решение уравнения – значение X, при котором f(x*) = 0  Рис. 1.1. График функции y = ƒ(x) Корень X* уравнения называется простым, если первая производная функции f(x) в точке X* не равна нулю, т. е.  Если же  то корень X* называет кратным. Геометрически корень уравнения есть точка пересечения графика функции y = ƒ(x) с осью абсцисс. На рис. 1.1. изображен график функции y = ƒ(x) имеющей четыре корня: два простых (x1* и x3*) и два кратных (x2* и x4* ). Этапы нахождения корней уравнения Большинство методов решения уравнения ƒ(x) = 0 ориентировано на отыскание простых корней уравнения. Рассмотрим основные этапы. В процессе приближенного отыскания корней уравнения (1.1) обычно выделяют два этапа: 1. Локализация корня. 2. Уточнение корня. Локализация корня – определение отрезка [a, b] , содержащего один и только один корень. Отрезок можно найти с помощью : – физического соображения. – построения графика или таблицы значений функции y = ƒ(x) На наличие корня на отрезке [a, b] указывает различие знаков функции на концах отрезка. Основанием для этого служит следующая теорема математического анализа. Если функция ƒ непрерывна на отрезке [a, b] и принимает на его концах значения разных знаков так, что ƒ(a) ۰ ƒ(b) < 0 , то отрезок [a, b] содержит по крайней мере один корень уравнения ƒ(x) = 0 . Замечание! Корень четной кратности таким образом локализовать нельзя, так как в окрестности такого корня функция ƒ(x) имеет постоянный знак. Уточнение корня – вычисление приближенного значения корня с заданной точностью .  Данное значение уточняется с помощью различных итерационных методов. Тема 2 К основным численным методам решения уравнений относятся такие методы, как метод половинного деления, метод простых итераций, метод касательных и метод хорд. Одним из основных численных методов является метод итераций, на принципах которого основаны остальные методы. Прежде чем использовать какой-либо численный метод, необходимо произвести отделение корней, т.е. определить количество корней в интересующей нас области и выделить достаточно малые интервалы, в каждом из которых заключен только один корень. Условием существования корня непрерывной функции на интервале является ƒ(a) ۰ ƒ(b) < 0 , что говорит о том, что на данном интервале функция изменяет знак, т.е. пересекает ось х. Метод половинного деления (дихотомии, бисекции) является самым простым и надежным способом решений нелинейного решения. Метод реализуется следующим алгоритмом. Пусть необходимо решить уравнение ƒ(x) = 0, где функция непрерывна на отрезке [a, b] и единственный корень X заключен в том же интервале. Разделим отрезок a, b пополам и получим  . Вычислим значение функции в этой точке (рис. 2.1) и проверим знак условия ƒ(x) ۰ ƒ(a) . Если знак условия положителен, то корень уравнения находится на отрезке [x, b] и левая граница интервала перемещается в точку X, т. е. A = X . Если знак условия отрицателен, то корень уравнения находится на отрезке [a, x] т. е. [b = x] Далее продолжаем вышеописанные шаги, т.е. новый отрезок вновь делим пополам и производим новый выбор. Процесс повторяем до тех пор, пока длина отрезка не станет меньше заданной точности   Рис. 2.1. График функции Число итераций при использовании этого метода значительно, и поэтому сходимость его медленная. Однако при любой ширине отрезка [a, b] сходимость гарантирована. Кроме того, простота реализации метода уменьшает число вспомогательных операций и частично компенсирует невысокое быстродействие. Метод простых итераций Метод простых итераций является популярным способом численного решения математических задач. Его суть – нахождение алгоритма поиска по известному приближению (приближенному значению) искомой величины следующего, более точного приближения. Метод реализуется следующим алгоритмом. Пусть уравнение ƒ(x) = 0, можно заменить эквивалентным ему уравнением  (2.1) Выберем на отрезке [a, b] начальное приближение Хо и подставим его в правую часть уравнения (2.1). На этом шаге мы получим уточненное значение .  Подставим теперь Х1 в уравнение (2.1) и получим новое приближение  Продолжая этот процесс неограниченно, получим последовательность приближений к корню:  (2.2) Процесс итераций сходится при условии .  Это условие является необходимым и достаточным. При  вне зависимости от выбора начального приближения процесс будет расходиться. Для выбора начального приближения  вычисляют значения первых производных функции в граничных точках интервала {a, b}, содержащего корень, и за начальное приближение принимают тот конец интервала, для которого выполняется условие .  Геометрически способ простых итераций можно представить следующим образом. Построим графики двух функций:y = x и  . Абсцисса точек пересечения этих графиков является корнем уравнения f(x) = 0 (рис. 2.2). Рис. 2.2. Графики функций  рис. 2.2 График функций y = x и 2.3. Метод касательных (Ньютона) Метод касательных (Ньютона) является наиболее эффективным методом решения нелинейных уравнений. Метод основан на замене f(x ) в точке начального приближения x = x0 касательной, пересечение которой с осью X дает первое приближение X1 и т.д. (рис. 2.3).  Рис. 2.3. График функции f(x) Уравнение касательной, проходящей через точку X0, имеет вид  Первое пересечение получим, взяв абсциссу точки пересечения этой касательной с осью OX, т. е. Y =0, X = X1  Аналогично поступаем с остальными точками и в результате получаем последовательность x1, x2, …. Xn  Метод обеспечивает быструю (квадратичную) сходимость. В качестве первого приближения X0 выбирают тот конец отрезка [a, b] , для которого выполняется условие ۰  Это условие сходимости является достаточным, но необходимым, т.е. если условие выполняется, то итерационный процесс обязательно сойдется, а если не выполняется, то может или сойтись, или не сойтись. Метод хорд является итерационным численным методом приближённого нахождения корня уравнения. Метод реализуется следующим алгоритмом. Пусть уравнение f(x) = 0 имеет один корень на отрезке [a, b] а первая и вторая производные функции определены, непрерывны и сохраняют постоянные знаки на этом интервале. Рассмотрим геометрическое представление метода (рис. 2.4).  Проведем хорду через точки A и B . В точке пересечения хорды с осью X находим значение функции F(x) и получаем точку A1. Затем проводим новую хорду через точки A1 и B и т.д. Уравнение прямой, проходящей через две точки X1 и X2, имеет вид (2.3)  Из этого уравнения необходимо определить точку Xk– это точка пересечения хорды с осью X. Следовательно, в уравнении прямой Yk = 0. Один из концов отрезка [a, b] является подвижным (в нашем случае A), другой конец B– неподвижный. Условием сходимости итерационного процесса является правильный выбор подвижного и неподвижного концов. Обозначим подвижный конец интервала X неподвижный конец –C В качестве подвижного конца выбирается точка, для которой выполняется условие ۰  Уравнение (2.3) можно записать в следующем виде:  Отсюда можно найти искомую точку , и это будет итерационной формулой метода:  Сравнение методов решения уравнений |