Численные методы решения уравнений
Методы хорд и итераций, правило Ньютона. Интерполяционные формулы Лагранжа, Ньютона и Эрмита. Точечное квадратичное аппроксимирование функции. Численное дифференцирование и интегрирование. Численное решение обыкновенных дифференциальных уравнений.
| Рубрика | Математика |
| Вид | курс лекций |
| Язык | русский |
| Дата добавления | 11.02.2012 |
| Размер файла | 871,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
72,88
+0,02
3
63,2
63,24
-0,04
4
54,7
54,76
-0,06
5
47,5
47,46
+0,04
6
41,4
41,32
+0,08
7
36,3
36,36
-0,06
Имеем
§13. Численное дифференцирование. Вычисление производной по её определению
Пусть функция y=f (x) определена в некоторой окрестности точки x0 и имеет производную в этой точке, т.е. существует предел отношения приращения функции к приращению аргумента при стремлении к нулю
(1).
Значение производной в точке x0 можно получить, переходя к пределу в (1) по последовательности целых чисел n и полагая, например Здесь (x) 0 - некоторое начальное приращение аргумента, - некоторое число, большее 1, n=0, 1, 2,…. Тогда значение производной функции f (x) в точке x0 запишется так:
Отсюда получим приближённое равенство
(2).
Для функции y=f (x), имеющей непрерывную производную до второго порядка включительно в окрестности точки x0, точность приближения производной соотношением (2) можно установить, воспользовавшись формулой Тейлора
.
Тогда
и окончательно имеем
.
Замечание. Для достижения заданной точности приближения производной при определённом числе вычислений можно использовать неравенство
(3).
Пример. Вычислить производную функции y=sin x в точке с точностью =10-3 (31,047198).
Решение:
Пусть,
тогда .
Определим приближённое значение производной:
(n=0,1,2,…).
Найдём отношения, аппроксимирующие производную
Итак, начиная с третьего приближения в соответствии с оценкой (3) получаем искомое приближение производной данной функции с точностью, не меньшей, чем заданное =0,001.
§14. Конечно-разностные аппроксимации производных
Пусть отрезок a, b] разбит на n, n2 равных частей точками xi, Разность между соседними значениями аргумента постоянна, то есть шаг Пусть на отрезке [a, b] определена функция y=f (x), значения которой в точках xi равны yi=f (xi), i=0,1,…,n.
Запишем выражения для первой производной функции в точке xi с помощью отношения конечных разностей:
a) аппроксимация с помощью разностей вперёд (правых разностей)
i=0,1,…n-1.
b) аппроксимация с помощью разностей назад (левых разностей)
c) аппроксимация с помощью центральных разностей (точка xi является центром системы точек xi-1, xi,, xi+1).
i=1,…, n-1.
Замечание 1. Аппроксимация производной с помощью центральных разностей представляет собой среднее арифметическое производных с помощью левых и правых разностей в точках xi,,
Замечание 2. Соотношения (a) и (c) не позволяют вычислить производную в точке xn=b, а (b) и (c) - в точке x0=a.
Теорема. для функции y=f (x), имеющей непрерывную производную до второго порядка включительно, погрешность аппроксимации производных разностями вперёд и назад имеет один и тот же порядок 0 (h), а погрешность аппроксимации центральными разностями для функции y=f (x), имеющей непрерывную производную до третьего порядка включительно, имеет порядок 0 (h2).
Доказательство:
Приближённое значение производной второго порядка в точке xi выразим через значение функции yi-1, yi,yi+1. Для этого представим вторую производную с помощью правой разности:
а производные первого порядка y'i+1 и - c помощью левых разностей:
и окончательно получим
(1).
Погрешность последней аппроксимации имеет порядок 0 (h2) для функции y=f (x), имеющей непрерывную производную до четвёртого порядка включительно на отрезке [a, b]. Естественно, представление (1) с помощью конечных разностей позволяет вычислить значения второй производной только во внутренних точках отрезка.
§15. Использование интерполяционных многочленов Лагранжа для формул численного дифференцирования
Пусть функция y=f (x) определена на отрезке [a, b] и в точках xi (i=0,1,2,…,n) принимает значения yi=f (xi).
Разность между соседними значениями аргумента xi постоянна и является шагом h=xi-xi-1 (i= разбиения отрезка на n частей, причём a=x0 и b=xn.
Найдём аппроксимации производных первого и второго порядков с помощью значений функции yi в узловых точках xi с погрешностью одного и того же порядка в зависимости от шага h, причём этот порядок не ниже, чем достигаемый при конечно-разностной аппроксимации производных для того же шага.
Для того, чтобы выразить значения производных через значения функции yi в узлах интерполяции xi, построим интерполяционный многочлен Лагранжа Lm (x) степени m, удовлетворяющий условиям: Lm (xk) =f (xk) =yk, k=i, i+1,…, i+m; i+m n. Многочлен Lm (x) интерполирует функцию f (x) на отрезке [xi, xi+1]. Дифференцируя многочлен Lm (x), получаем значения производных в точках xk, k=i, i+1,…, i+m.
Если m=1, то L1 (x) - линейная функция, график которой проходит через точки (xi,yi) и (xi+1,yi+1). Тогда
, .
Если m=2, график интерполяционного многочлена Лагранжа L2 (x) - парабола, проходящая через три точки (xi, yi), (xi+1,yi+1), (xi+2, yi+2) Вычислим первую и вторую производные многочлена L2 (x) на отрезке (xi,xi+2):
Первая и вторая производные многочлена Лагранжа L2 (x) в точках xi, xi+1, xi+2 являются приближениями производных соответствующих функции f (x) в этих точках:
(1).
(2).
Если функция f (x) на отрезке [xi, xi+2] имеет непрерывную производную до третьего порядка включительно, то справедливо представление функции в виде суммы f (x) =L2 (x) +R2 (x) (3), где R2 (x) - остаточный член интерполяционной формулы, причём
xi, xi+2)
В этом случае можно дать оценку погрешности приближений производных соотношениями (1) и (2). Дифференцируя (3), получим
(4)
(5)
Здесь
,
(xi, xi+2) (6)
, (7)
Погрешности при вычислении производных в точках xi, xi+1, xi+2 определяются следующими значениями остатков:
(8)
(9)
Следствие 1. Таким образом, равенство (8) показывает, что погрешности аппроксимации первой производной f ' (x) c помощью формул (1) имеют один и тот же порядок 0 (h2) и естественна следующая рекомендация по их применению на отрезке [a, b] в точках xi, i=0,1,2,…, n при n2
(10)
Следствие 2. Из равенства (9) следует, что приближение второй производной с помощью формулы (2) имеет различный порядок в зависимости от h в разных точках: в точках xi и xi+2 имеет погрешность порядка h, а в точке xi+1 порядок погрешности выше
Пример. Значения функции y=sin x определены таблицей
|
x |
0 |
|||
|
sin x |
0 |
0,5 |
0,866 |
С помощью формул (1) и (2) приближения найти y' (0) и y'' (0) и оценить погрешность результатов вычислений.
Решение:
0<.
Так как ,
то
Итак 0,09 (точное значение y' (0) =cos 0=1. Теперь воспользуемся формулой (2):
.
Как видим, для лучшей оценки производной второго порядка необходимо увеличить число узловых точек и выбрать меньший шаг.
§16. Численное интегрирование.Формула прямоугольников
Для приближённого вычисления определённого интеграла разобьём отрезок интегрирования [a, b] на n равных частей точками x0=a, x1=x0+h,…, xi+1=xi+h,…,xn=b
(h - шаг разбиения, ). Значения функции f (x) в точках разбиения xi обозначим yi. Непрерывная подинтегральная функция y=f (x) заменяется сплайном (кусочно-полиномиальной функцией) S (x), аппроксимирующей данную функцию. Интегрируя функцию на отрезке [a, b], придём к некоторой формуле численного интегрирования (квадратурной формуле).
В зависимости от функции S (x), аппроксимирующей подинтегральную функцию, будем получать различные квадратурные формулы.
Если на каждой части [xi-1, xi], i=деления отрезка [a, b] функцию f (x) заменить функцией, принимающей постоянное значение, равное, например, значению функции f (x) в серединной точке i-й части, то есть то функция S (x) будет иметь ступенчатый вид:
.
В этом случае и получаем квадратурную формулу прямоугольников
(1).
Пример. Найти приближённое значение интеграла по формуле прямоугольников.
Решение. Пусть n=10.
Тогда x0=0, …, x10=1.
,
=
Погрешность квадратурной формулы оценивается величиной остаточного члена R (h), зависящего от шага разбиения h (или от числа разбиений n).
где 0сh.
Если то Заменим h на x и проинтегрируем неравенство на отрезке [0, h]:
Но легко заметить, что тогда откуда: , где . Получаем общую погрешность на [a, b]
(так как hn= b - a).
§17. Формула трапеций
Если функцию f (x) на каждом отрезке [xi-1, xi] заменить её линейной интерполяцией по точкам (xi-1,yi-1), (xi, yi) то получим непрерывную кусочно-линейную функцию
.
Здесь yi=f (xi). Графиком этой функции является ломаная линия. В этом случае
и получаем квадратурную формулу трапеций:
таким образом:
(1).
Оценка погрешности этой формулы:
где , а
тогда
а общая погрешность на [a, b] тогда равна
.
§18. Формула Симпсона (парабол)
Рассмотрим точки A (-h, y-1), B (0, y0), C (h, y1). Уравнение параболы, проходящей через эти точки: y=a+bx+cx2
(1)
Площадь параболы, проходящей через точки A, B, и С вычисляется по формуле:
(2).
Из (1), сложив первое и третье равенства, найдём:
откуда
2ch2=y-1-2y0+y1 и тогда .
Рассмотрим теперь функцию y=f (x), заданную на [a, b]. Требуется вычислить Разобьём отрезок [a, b] на 2n отрезков a=x0<x1<…<x2n=b. Заменим дугу кривой y=f (x) () параболой, проходящей через эти точки и тогда площадь криволинейной трапеции, ограниченной сверху параболой, будет вычисляться по формуле:
.
Вычислим площадь следующей криволинейной трапеции на [x2, x4]:
и так далее. Искомая площадь будет приближённо равна:
Оценка погрешности для формулы Симпсона (без вывода):
Пример 1. Найти приближённое значение интеграла с помощью квадратурных формул прямоугольников, трапеций и Симпсона, если отрезок [0, 1] разбит на 10 равных частей.
Решение:
.
При n=10 получим следующие оценки величин погрешности результатов:
Пример 2. Вычислить интеграл . по формуле Симпсона.
Решение: Возьмём .
. Тогда .
§19. Приемы приближенного вычисления несобственных интегралов
Рассмотрим интегралы вида:
(1), (2), (3).
Для случая (3) функция f (x) имеет бесконечный разрыв либо в точке x=a, либо x=b, либо x=c [a, b]. Вычисляемые несобственные интегралы при этом предполагаются сходящимися.
Одним из источников получения численных значений несобственных интегралов (1) и (2) являются квадратурные формулы вида: (Гаусса-Кристоффеля). Для их применения нужно выделить под интегралом подходящую весовую функцию и воспользоваться соответствующей квадратурой.
Тогда для интеграла (1):
- формула Лагерра,
где , Ln-1 - n-1-ый многочлен Лагерра.
Аналогично, для интеграла (2) имеем:
- формула Эрмита,
где , Hn-1 - n-1-вый многочлен Эрмита.
К вычислению интегралов с бесконечной верхней границей можно применять различные формулы численного интегрирования, пользуясь равенством, определяющим несобственный интеграл:
.
Оно позволяет считать, что для достаточно больших значений b выполняется и вычислять интеграл с помощью известных квадратурных правил. предполагая исходный интеграл абсолютно сходящимся, величину абсолютной погрешности, то есть , за счет увеличения b можно сделать как угодно малой.
В случае (2) без ограничения общности можно считать, что подынтегральная функция имеет особенность на границе промежутка интегрирования, то есть если точкой c, где f (x) обращается в бесконечность, окажется внутренняя точка интервала (a, b), то данный интеграл можно представить символически как . Также без потери общности, достаточно рассматривать . Но к таким интегралам, в которых подынтегральная функция имеет особыми точками значения - 1 и (или) 1, можно применить квадратурную формулу Эрмита (Мелера) в виде
=
или более общую формулу, где параметры > - 1, > - 1 желательно подобрать так, чтобы функция была как можно более гладкой. Такой прием при вычислении несобственных интегралов называют мультипликативным выделением особенностей. Существует несколько специальных квадратурных формул, позволяющих "загнать" в весовые функции различные типы особенностей: степенную, логарифмическую и другие.
Применяются и другие приемы вычисления несобственных интегралов. Надо отметить, что иногда достаточно сделать удачную замену переменной, чтобы преобразовать несобственный интеграл к более подходящему для вычисления виду.
§20. Численное решение обыкновенных дифференциальных уравнений. Понятие о численном решении задачи Коши
Дифференциальное уравнение первого порядка, разрешённое относительно производной имеет вид
(1).
Решением дифференциального уравнения называется функция (x), подстановка которой в уравнение обращает его в тождество:
График решения называется интегральной кривой. Например, решением уравнения является функция при любом значении произвольной постоянной С.
Задача Коши для дифференциального уравнения (2) состоит в том, чтобы найти решение этого уравнения, удовлетворяющее начальному условию
(2).
Пару чисел называют начальными данными. Решение задачи Коши называют частным решением уравнения (1) при условии (2).
Пример:
частным решением задачи Коши является функция .
Частному решению соответствует одна из интегральных кривых, проходящая через точку .
Условия существования и единственности решения задачи Коши содержатся в следующей теореме.
Теорема. Пусть функция f (x, y) - правая часть дифференциального уравнения (2) - непрерывная вместе со своей частной производной в некоторой области D на плоскости. Тогда при любых начальных данных задача Коши (1) - (2) имеет единственное решение .
При выполнении условий теоремы через точку на плоскости проходит единственная интегральная кривая. Будем считать, что условия теоремы существования и единственности выполняются. Численное решение задачи Коши (1) - (2) состоит в том, чтобы искомое решение получить в виде таблицы его приближённых значений для заданных значений аргумента x на некотором отрезке (a, b): а=x0, x1, x2,…,xm=b (3).
Точки (3) называют узловыми точками, а множество этих точек называют сеткой на отрезке [a, b]. Будем использовать равномерную сетку с шагом h. или . Приближённые значения численного решения задачи Коши в узловых точках xi обозначим yi; таким образом,
Для любого численного метода решения задачи Коши начальное условие (2) выполняется точно, то есть
Величина погрешности численного метода решения задачи Коши на сетке отрезка [a, b] оценивается величиной , то есть расстоянием между векторами приближённого решения (y0, y1, …, ym) и точного решения на сетке по m-норме.
Определение. численный метод имеет p-й порядок точности по шагу h на сетке, если расстояние d можно представить в виде степенной функции от h: d=chp, p>0, где c-некоторая положительная постоянная, зависящая от правой части уравнения (1) и от рассматриваемого метода.
В данном случае очевидно, что когда h cтремится к нулю, погрешность d также стремится к нулю.
§21. Метод Эйлера
Простейшим численным методом решения задачи Коши (1) - (2) (§20) является метод Эйлера, называемый иногда методом ломаных Эйлера.
Угловой коэффициент касательной к интегральной кривой в точке P0 (x0,y0) есть . Hайдём ординату y1 касательной, соответствующей абциссе x1=x0+h. Так как уравнение касательной к кривой в точке P0 имеет вид то Угловой коэффициент в точке P1 (x1,y1) также находится из данного дифференциального уравнения На следующем шаге получаем новую точку P2 (x2, y2), причём
Продолжая вычисления в соответствии с намеченной схемой, получим формулы Эйлера для m приближённых значений решения задачи Коши с начальными данными (x0, y0) на сетке отрезка [a, b] с шагом h: (1).
Графической иллюстрацией приближённого решения является ломаная, соединяющая последовательно точки P0, P1, P2, …,Pm, которую называют ломаной Эйлера.
Оценим погрешность метода Эйлера на одном шаге. Для этого запишем разложение точного решения задачи Коши в точке x1 по формуле Тейлора с дополнительным членом в форме Лагранжа:
,
Погрешность метода на одном шаге имеет h2, т.к.
После m шагов погрешность вычисления значения ym в концевой точке отрезка возрастёт не более чем в m раз. Погрешность метода Эйлера можно оценить неравенством
или представить в виде
, где
Это означает, что метод Эйлера имеет первый порядок точности. В частности, при уменьшении шага h в 10 раз погрешность примерно уменьшится в 10 раз.
Практическую оценку погрешности решения, найденного на сетке с шагом , в точке производят с помощью приближённого равенства-правила Рунге:
(2)
где p-порядок точности численного метода. Таким образом, оценка полученного результата по формуле (2) вынуждает проводить вычисления дважды: один раз с шагом h, другой - с шагом.
Пример. Решить задачу Коши методом Эйлера на отрезке [0; 0,4]. Найти решение на равномерной сетке с шагом h1=0,1, h2=0,05 в четырёх узловых точках. Аналитическое решение задачи имеет вид .
Решение: Здесь m=4, a=0, b=0,4 Используя рекуррентные формулы x0=0, y0=1, xi=xi-1+0,1; yi=yi-1+0,1 (xi-1+yi-1); i=1,2,3,4 последовательно находим
при i=1: x1=0,1; y1=1+0,1 (0+1) =1,1
при i=2: x2=0,2; y2=1,1+0,1 (0,1+1,1) =1,22
при i=3: x3=0,3; y3=1,22+0,1 (0,2+1,22) =1,362
при i=4: x4=0,4; y4=1,362+0,1 (0,3+1,362) =1,5282
Обозначим , и представим результаты вычислений в таблице:
|
i |
xi |
yi (h) |
yi |
(xi) |
di |
||
|
1 |
0,1 |
1,1 |
1,105 |
1,110342 |
0,005 |
0,005332 |
|
|
2 |
0,2 |
1,22 |
1,231012 |
1,242805 |
0,011012 |
0,011793 |
|
|
3 |
0,3 |
1,362 |
1,380191 |
1,399718 |
0,018191 |
0,019527 |
|
|
4 |
0,4 |
1,5282 |
1,554911 |
1,583649 |
0,026711 |
0,028738 |
Отметим, что оценка погрешностей решения , вычисляемых по формулам (2), близки к отклонениям di и обе величины достигают значения -ошибки метода Эйлера при вычислении с шагом 0,05. Для сравнения заметим, что погрешность при вычислениях с шагом 0,1 составляет .
§ 22. Методы Рунге - Кутта
Определение. Численные методы решения задачи Коши на равномерной сетке (x0=a, x1, x2,…, xm=b) отрезка [a, b] с шагом называются методами Рунге - Кутта, если, начиная с данных (x0, y0), решение ведётся по следующим рекуррентным формулам:
(1)
)
Метод называется методом Рунге - Кутта порядка p, если он имеет p-й порядок точности по шагу h на сетке. Порядок точности p достигается с помощью формул (1) при определённых значениях коэффициентов cj и dj (j=1,2,.,p); причем c1 всегда полагают равным нулю. Эти коэффициенты вычисляются по следующей схеме:
1) точное решение и его приближение представляют в виде разложения по формуле Тейлора с центром x0 вплоть до слагаемого порядка hp+1;
2) из равенств подобных членов при одинаковых степенях h в двух разложениях получают уравнения, решая которые находят коэффициенты cj и dj.
Замечание 1. что метод Эйлера можно назвать методом Рунге - Кутта первого порядка.
Покажем это. Пусть p=1, c1=0, d1=1, формулы (1) преобразуются в соотношения: xi=xi-1+h, yi=yi-1+yi-1, i=1,2, …, m
или
.
Замечание 2. Метод Рунге-Кутта второго порядка можно назвать методом Эйлера - Коши. Покажем это. Пусть p=2, c1=0, c2=1, d1=d2=. Алгоритм метода Эйлера - Коши получается из формул (1):
xi=xi-1+h, yi=
(2)
Для практической оценки решения можно применять правило Рунге, полагая в приближённом равенстве (правиле Рунге) p=2.
Пример. Решить задачу Коши y'=x+y, методом Эйлера - Коши на отрезке [0; 0,4]. Найти решение на равномерной сетке с шагом 0,1 в четырёх узловых точках.
Решение. Формулы (2) в данном случае примут вид:
Полагая x0=0, y0=1 при i=1 последовательно находим
;
;
при i=2
.
Далее получаем: при i=3, x3=0,3 - y3=1,398405, при i=4, x4=0,4 - y4=1,581804.
Погрешность полученного решения не превышает величины
Замечание 3. Метод Рунге - Кутта четвёртого порядка называют классическим методом Рунге - Кутта.
Пусть p=4, c1=0, c2=c3= c4=1, d1=d4=, d2=d3=. Из рекуррентных формул (1) получим алгоритм решения задачи Коши классическим методом Рунге - Кутта:
(3)
Графиком приближённого решения является ломаная, последовательно соединяющая точки Pi (xi,yi) (i=0,1,…,m). С увеличением порядка численного метода, звенья ломаной приближаются к ломаной, образованной хордами интегральной кривой y= (x), последовательно соединяющими точки (xi, (xi)) на интегральной кривой.
Правило Рунге практической оценки погрешности решения для численного метода четвёртого порядка имеет вид:
Пример. Решить задачу Коши y'=x+y, классическим методом Рунге - Кутта на отрезке [0; 0,4]. Найти решение на равномерной сетке с шагом 0,1 в четырёх узловых точках.
Решение: Так как f (x,y) =x+y, то согласно формулам (3) получаем
;
;
Полагая x0=0, y0=1, последовательно находим при i=1:
0,1 (0+0,05+1+0,055) =0,1105
0,1 (0+0,1+1+0,1105) =0,121050
x1=0+0,1=0,1; y1=
при i=2:
=0,1 (0,1+0,05+1,110342+0,0605171) =0,1320859
=0,1 (0,1+0,05+1,110342+0,06604295) =0,1326385
=0,1 (0,1+0,1+1,110342+0,1326385) =0,1442980
x2=0,1+0,1=0,2; y2=.
Далее получаем при i=3, x3=0,3, y3=1,399717; при i=4, x4=0,4; y4=1,583648.
Погрешность полученного решения не превышает величины
§23. Приближенное решение систем уравнений. Приближенное решение систем линейных уравнений
Рассмотрим сущность итерационного метода при решении систем линейных уравнений на примере. Пусть дана система Ax=B, где А= (аij) - матрица коэффициентов при переменных хij размерности nn, x= (x1, x2, …, xn) - матрица переменных, - матрица свободных членов. Она может быть преобразована к эквивалентной ей системе вида x=Bx+c, где В и с - некоторые новые матрица и свободный член соответственно. Данную систему можно трактовать как задачу о неподвижной точке линейного отображения В в пространстве Rn и определить последовательность приближений х (k) к неподвижной точке х* рекуррентным равенством x (k+1) =Bx (k) +c, k=0, 1, 2, …. Итерационный процесс, начинающийся с некоторого значения называется методом простых итераций.
Пусть исходная линейная система уравнений имеет вид:
(1)
При решении этой системы необходимо:
I. Задать начальное приближенное решение (индекс в скобках указывает номер итерации), которое будет уточняться в процессе итераций. При этом надо учитывать, что, если метод сходится, то он сходится при любом начальном приближении. Обычно в качестве начального приближения, в зависимости от задачи, берутся либо вектор правых частей и тогда , либо нулевой вектор и тогда .
II. Привести исходную систему (1) к виду, удобному для проведения итераций, то есть к виду
(2)
где - произвольные линейные функции переменных , причем некоторые переменные могут отсутствовать в правых частях системы (2), но каждая переменная должна присутствовать в левой части соответствующего уравнения.
III. Указать совокупность действий, которые составляют одну итерацию (переход от к ). Достаточно рассмотреть два алгоритма вычисления корней уравнений системы.
Метод простой итерации записывается в виде:
(3)
Метод Зейделя (обобщение метода простой итерации) заключается в следующем: уже полученные значения переменных используются при вычислении остальных искомых переменных на этой итерации. То есть имеет место:
(4)
Применяя каждый из методов, необходимо учитывать, что метод Зейделя сходится на порядок быстрее метода простой итерации.
IV. Выяснить условия сходимости итерационного процесса. При решении практических задач используется следующая теорема: Если матрица А исходной системы имеет диагональное преобладание, то методы простой итерации и Зейделя сходятся.
V. Указать условия окончания итерационного процесса. В этой роли обычно выступает оценка , где е - наперед заданная точность вычислений.
§24. Приближенные методы решения систем нелинейных уравнений
Многие практические задачи при их математическом моделировании сводятся к решению системы нелинейных уравнений. Система n нелинейных уравнений с n неизвестными в общем случае имеет вид
(1)
Решением системы уравнений (1) называется n чисел которые при подстановке в (1) обращают все уравнения в нули.
Задача (1) тесно связана с другой очень часто встречающейся задачей - минимизации функции многих переменных
(2)
Эта связь проявляется в том, что каждую из этих задач можно свести к решению другой. Пусть, например, вектор является решением системы (1). Построим функцию
(3)
Так как обращает в нуль все уравнения системы (1), то обращает функцию в нуль. Поскольку , то обращает функцию Q в минимум, и этот минимум равен нулю. Справедливо и обратное утверждение. Пусть совокупность чисел обращает функцию в минимум, равный нулю. Тогда каждый член суммы, входящий в (3), обращается в нуль и, следовательно, совокупность является решением системы (1). Таким образом, задача (1) сводится к нахождению минимума (3).
В свою очередь, для задачи минимизации (2) точка минимума является решением системы нелинейных уравнений.
Возможность сведения одной задачи к другой не означает, что можно ограничиться рассмотрением только одной из них. Каждая из них является весьма сложной и имеет многочисленные подводные камни, которые проявляются при практической реализации существующих методов их решения. По-видимому, не существует никаких универсальных методов решения этих задач. Установление связи между задачами (1) и (2) удобно тем, что в каждом конкретном случае мы можем использовать ту из них, которая быстрее приводит к цели при располагаемых ресурсах вычислительной техники и математического обеспечения. Трудности при решении систем нелинейных уравнений проявляются в следующем:
Определение количества корней системы и их отделение проводить достаточно сложно в силу невозможности при больших n использовать простые геометрические соображения.
Многие надёжные методы нахождения корня одного нелинейного уравнения, имеющие гарантированную сходимость, такие как метод половинного деления или метод хорд и т.д., не допускают обобщения на случай n неизвестных.
Решение системы (1) ищут, как правило, методом итераций или эффективным по скорости методом Ньютона, сходимость которых возможна только при наличии хорошего начального приближения.
нахождение хорошего начального приближения для сложной системы (1) является весьма непростым делом и требует, помимо математического анализа системы, привлечение других соображений (физических, инженерных, экономических и др.), связанных с постановкой решаемых задач.
Замечание 1. никаких универсальных методов преодоления отмеченных трудностей и решения этих задач не существует. Каждый раз приходится, наряду с теоретическими исследованиями системы (1), использовать эвристические соображения и проводить экспериментальные численные исследования. Рассмотрим названные в пункте 3 методы.
Метод простой итерации.
Запишем систему (1) в виде, удобном для итераций:
(4)
Зададим начальное приближенное решение (индекс в скобках указывает номер итерации), которое будет уточняться в процессе итераций. При этом надо учитывать, что, если метод сходится, то он сходится при любом начальном приближении. Первое приближение вычисляется по формулам:
,
где - нелинейные функции переменных . Затем полученное первое приближение подставляем в правую часть системы (4) и вычисляем второе приближение, и так далее. В общем случае формулы метода простой итерации можно записать в виде:
(5)
В роли условия окончания итерационного процесса. обычно выступает оценка (6), где е - наперед заданная точность вычислений.
Уравнение (4) удобно записать в векторном виде: (7)
где - вектор-столбец искомого решения, а Ф - вектор-функция
Итерационный процесс (5) можно также записать в векторном виде
. (8)
Условия сходимости итерационного метода (5) (или в векторном виде (8) определяется принципом сжатых соображений: если отображение (7), задаваемое вектор-функцией Ф будет сжатым, то итерационный процесс (8) сходится при условии, что начальное приближение достаточно близко к корню.
Достаточное условие сходимости метода простой итерации.
Рассмотрим матрицу Якоби для преобразования (4)
(9)
Матрица Якоби (или якобиан) зависит от переменных
Теорема. если матрица Якоби в точке , которая даёт решение системы (4), и в некоторой её окрестности имеет все собственные значения, по модулю меньше единицы , то метод простой итерации сходится.
Замечание 2. Для выполнения этого условия достаточно, например, выполнения следующих неравенств для элементов матрицы Якоби
(10)
где q - некоторое положительное число, меньшее единицы, т.е. Неравенства (10) должны выполнятся в точке и в некоторой её окрестности.
Возможно естественное обобщение метода простой итерации (5), аналогичное методу Зейделя для систем линейных уравнений. Оно заключается в том, что переменные , уже полученные на данном итерационном шаге, используются для получение других величин на этом шаге. Соответствующие формулы имеют вид
(11)
Если бы оба метода (5) и (11) сходятся, то метод (11) сходится, вообще говоря, быстрее, так как получаемые на каждом шаге итерации новые значения переменных сразу используются в дальнейших вычислениях на этом шаге.
Метод Ньютона и его модификации.
Метод Ньютона - метод, который сводит решение системы нелинейных уравнений к последовательному решению систем линейных уравнений для нахождения поправок к предыдущим приближениям.
Рассмотрим общий вид нелинейной системы (1). Зададим начальное приближение . Будем искать решение системы (1) в виде
(12)
Разложим левые части системы (1) в ряд Тейлора в точке , считая величины малыми и в силу этого ограничиваясь только линейными членами в ряде Тейлора. Для функции получим
=, (i=1,2,…,n) (13)
Обозначение указывает, что соответствующая частная производная вычисляется в базовой точке , для которой записывается разложение в ряд Тейлора. Поскольку является точным решением системы (1), левые части в уравнениях (13) равны нулю. В результате для неизвестных приращений получим систему линейных уравнений
(14)
Матрицей этой системы является якобиан.
(15)
Если определитель этой матрицы не равен нулю, то из системы уравнений (14) можно найти неизвестные приращения . Поскольку в разложении Тейлора мы отбросили все члены, кроме линейных, соотношения (12) определяют не точное решение , а уточнение к нулевому приближению
,
или в координатном виде:
(16).
Один шаг метода Ньютона заключается в решении системы линейных уравнений (14), все коэффициенты которой и правые части зависят от начального приближения , и в получении уточнённого решения по формулам (16). Приняв теперь полученное первое приближение за начальное и проделав те же операции, которые были сделаны на первом шаге, можно получить следующее приближение к решению Этот итерационный процесс продолжается до тех пор, пока все получаемые приращения становятся малыми по абсолютной величине
(17)
Систему линейных уравнений, которую необходимо решать на каждом шаге метода Ньютона, в общем виде можно записать следующим образом:
(18)
Индекс k у частных производных указывает, что соответствующая частная производная вычисляется при (для значений искомых переменных на k-ой итерации).
Решив эту линейную систему и определив из неё величины поправок находим следующее приближение
(19)
выражения (18) и (19) полностью определяют один шаг метода Ньютона. Таким образом, метод Ньютона сводит решение систем нелинейных уравнений к многократному решению систем линейных уравнений (18).
Замечание 3. если метод Ньютона сходится, то сходимость имеет второй порядок, как и в случае уравнения с одной неизвестной.
Для сходимости метода требуется, чтобы начальное приближение было близко к точному решению, а функции и их первые и вторые производные удовлетворяли некоторым ограничениям. Несмотря на быструю сходимость, метод Ньютона имеет существенный недостаток: на каждом его шаге требуется вычислять n2 частных производных , определяющих коэффициенты при неизвестных в линейной системе (18), то есть якобиан. В то же время в методе простой итерации (5) требуется вычислять всего n функций Чтобы компенсировать этот недостаток метода Ньютона, были предложены различные его упрощения. Идея большинства из этих упрощений заключается в том, чтобы матрицу коэффициентов линейной системы (18) вычислять не на каждом итерационном шаге, а лишь на некоторых из них, считая на остальных шагах все элементы якобиана постоянными, равными их последним вычисленным значениям на том шаге, на котором производится пересчёт всех членов. В простейшем случае якобиан вычисляется один раз, в начальной точке , а затем якобиан остаётся постоянным в течение всего итерационного процесса. Такой метод обычно называется упрощённым методом Ньютона. Матрица коэффициентов линейной системы (18) в этом случае остаётся постоянной, и в процессе итераций изменяются только правые части системы, которые пересчитываются на каждом шаге итераций и решения системы , после нахождения которых происходит пересчёт по формулам (19). Конечно, этот метод сходится медленнее, чем метод Ньютона, но на каждом итерационном шаге требуется гораздо меньше арифметических операций.
Размещено на Allbest.ru
Подобные документы
Решение нелинейных уравнений методом касательных (Ньютона), особенности и этапы данного процесса. Механизм интерполирования функции и численное интегрирование. Приближенное решение обыкновенных дифференциальных уравнений первого порядка методом Эйлера.
курсовая работа [508,1 K], добавлен 16.12.2015Методы численного интегрирования, основанные на том, что интеграл представляется в виде предела суммы площадей. Геометрическое представление метода Гаусса с двумя ординатами. Численные примеры и сравнение методов. Решение систем алгебраических уравнений.
курсовая работа [413,4 K], добавлен 11.06.2014Решение систем линейных алгебраических уравнений методом простой итерации. Полиномиальная интерполяция функции методом Ньютона с разделенными разностями. Среднеквадратическое приближение функции. Численное интегрирование функций методом Гаусса.
курсовая работа [2,4 M], добавлен 14.04.2009Приближенные числа и действия над ними. Решение систем линейных алгебраических уравнений. Интерполирование и экстраполирование функций. Численное решение обыкновенных дифференциальных уравнений. Отделение корня уравнения. Поиск погрешности результата.
контрольная работа [604,7 K], добавлен 18.10.2012Предмет и методы изучения дифференциальной векторно-матричной алгебры, ее структура. Векторное решение однородных и неоднородных дифференциальных уравнений. Численное решение векторно-матричных уравнений. Формулы построения вычислительных процедур.
реферат [129,3 K], добавлен 15.08.2009Формирование системы их пяти уравнений по заданным параметрам, ее решение методом Гаусса с выбором главного элемента. Интерполяционный многочлен Ньютона. Численное интегрирование. Решение нелинейных уравнений. Метод Рунге-Кутта четвертого порядка.
контрольная работа [115,5 K], добавлен 27.05.2013Решение нелинейных уравнений. Отделения корней уравнения графически. Метод хорд и Ньютона. Система линейных уравнений, прямые и итерационные методы решения. Нормы векторов и матриц. Метод простых итераций, его модификация. Понятие про критерий Сильвестра.
курсовая работа [911,6 K], добавлен 15.08.2012Смысл метода Ньютона для решения нелинейных уравнений. Доказательства его модификаций: секущих, хорд, ложного положения, Стеффенсена, уточненного для случая кратного корня, для системы двух уравнений. Оценка качества метода по числу необходимых итераций.
реферат [99,0 K], добавлен 07.04.2015Общая постановка задачи решения обыкновенных дифференциальных уравнений, особенности использования метода Адамса в данном процессе. Решение системы обыкновенных дифференциальных уравнений методом Адамса и точным методом, сравнение полученных результатов.
курсовая работа [673,6 K], добавлен 27.04.2011Методы численного дифференцирования. Вычисление производной, простейшими формулами. Численное дифференцирование, основанное на интерполяции алгебраическими многочленами. Аппроксимация многочленом Лагранжа. Дифференцирование, с использованием интерполяции.
курсовая работа [1,3 M], добавлен 15.02.2016
