Метод Ньютона для решения систем нелинейных алгебраических уравнений.
Пусть известно некоторое приближение к корню . Запишем исходную систему нелинейных уравнений в виде
где . Разлагая эти уравнения в ряды и ограничиваясь первыми дифференциалами, т.е. линеаризуя функцию, получим
Это система уравнений, линейных относительно приращений ; все коэффициенты системы выражаются через последнее приближение . Решив эту систему, например, методом исключения найдем новое приближение .
Отметим, что система (6.13) в матричной форме имеет вид:
где значения производных в матрице коэффициентов и функций в векторе свободных членов вычислены при текущем приближении корня .
Матрица частных производных носит название матрицы Якоби. Для ее формирования возможны два пути: а) получить аналитические выражения для всех частных производных и вычислить их значение при – прием предпочтительный в смысле корректности подхода, но зачастую трудоемкий, особенно при большом числе аргументов; б) заменить частные производные в матрице Якоби их приближенными конечно-разностными значениями
где – малое приращение .
Алгоритм решения системы нелинейных уравнений методом Ньютона складывается из следующих этапов:
1) задают относительную погрешность вычисления аргументов , вектор начальных приближений , максимальное число итераций M для выхода из алгоритма в случае медленной сходимости или программных ошибок пользователя;
2. вычисляют матрицу Якоби по аналитическим выражениям или конечно-разностным методом, причем в последнем случае можно принять
3. решают систему линейных алгебраических уравнений (6.14) относительно приращений
4) вычисляют уточненное значение аргументов – новое приближение по формуле
5) проверяют выполнение условий по всем аргументам и если хотя бы одно выполняется, то возвращаются к п.2 для новой итерации; в противном случае полученный вектор считают решением.
Индивидуальные задания.
Индивидуальное задание 1. Решить уравнение методом дихотомии.
| № п/п | Уравнение | A | B | № п/п | Уравнение | A | B |
| Tg(x) = 1/x | p/2 | Tg(x) = 1/x2 | p/2 | ||||
| Ln(x) = 1/x | Ln(x) = Sin(x) | ||||||
| e-x = x | e-x = Sin(x) | p/2 | |||||
| Ln(x) = 1/ x2 | ex = 1/Sin(x) | p/2 | |||||
| e-x2 = x | e-x = x2 | ||||||
| 2 + Ln(x) = 1/x2 | |||||||
| 2 +Ln(x) = 1/x | Ln(x) = Sin2(x) | p/2 | |||||
| x - x3 + 1 = 0 | x - x3 + 2 = 0 | ||||||
| x + 3 = x3 | x + 5 = x3 | ||||||
| x + x3 - 5 = 0 | x - 0,5 = x8 | 0,5 | |||||
| 2x + x5 - 1 = 0 | x - 1 = x0,15 | ||||||
| 1 - x2 - x1,5 =0 | 1 - x2 = x4/3 | ||||||
| x +0,5 = e-x2 | x + 0,5 = e-x | ||||||
| 1 - x + x3 = 0 | -2 | 2 - x + x3 = 0 | -2 | ||||
| 1 + x = x3 | Sin(x) = 1/x | p/2 |
Индивидуальное задание 2. Решить систему уравнений методом Ньютона. Погрешность для всех вариантов принять e=0,1.
| № вар | Система | № вар | Система | ||
Лабораторные работы.
Лабораторная работа №5. Реализация методов решения уравнений и их систем средствами VBA.
Задание 1. Внести необходимые изменения в процедуры выполнения шага жордановых исключений, написанные в предыдущих лабораторных работах, чтобы с их помощью можно было решать системы линейных уравнений. Т.е. реализовать метод транспозиции. Используя эту процедуру, решить задачу индивидуального задания 1.
Задание 2. Используя формулы метода Гаусса и формулы массивов в Excel, подготовьте лист для решения системы линейных уравнений по образцу, представленному ниже:
| Решение системы линейных уравнений методом Гаусса | |||||||||||
| 1. Прямой ход метода Гаусса | 2. Обратный ход метода Гаусса | ||||||||||
| Матрица коэффициентов А | вектор В | Х | |||||||||
| 0,186 | |||||||||||
| 0,779 | |||||||||||
| -0,636 | |||||||||||
| 0,457 | |||||||||||
| 3.Проверка | |||||||||||
| Матрица коэффициентов А | Х | B=A*X | |||||||||
| 0,5 | -7,5 | -8 | 1,5 | 0,186 | |||||||
| -4,5 | -16,5 | -12 | 1,5 | 0,779 | |||||||
| -1,5 | -9,5 | -3 | 3,5 | -0,636 | |||||||
| 0,457 | |||||||||||
| 0,5 | -7,5 | -8 | 1,5 | ||||||||
| -84 | -84 | ||||||||||
| -32 | -27 | ||||||||||
| 0,5 | -7,5 | -8 | 1,5 | ||||||||
| -84 | -84 | ||||||||||
| 2,286 |
Рис.3 Рабочий лист для решения СЛУ методом Гаусса.
В качестве образца создание формул ознакомьтесь с формулами первого шага прямого хода исключения (Рис 4.):
Прямой ход метода Гаусса
Матрица коэффициентов А вектор В
| =A4:E4- $A$3:$E$3* (A4/$A$3) | =A4:E4- $A$3:$E$3* (A4/$A$3) | =A4:E4- $A$3:$E$3* (A4/$A$3) | =A4:E4- $A$3:$E$3* (A4/$A$3) | =A4:E4- $A$3:$E$3* (A4/$A$3) | |
| =A5:E5- $A$3:$E$3* (A5/$A$3) | =A5:E5- $A$3:$E$3* (A5/$A$3) | =A5:E5- $A$3:$E$3* (A5/$A$3) | =A5:E5- $A$3:$E$3* (A5/$A$3) | =A5:E5- $A$3:$E$3* (A5/$A$3) | |
| =A6:E6- $A$3:$E$3* (A6/$A$3) | =A6:E6- $A$3:$E$3* (A6/$A$3) | =A6:E6- $A$3:$E$3* (A6/$A$3) | =A6:E6- $A$3:$E$3* (A6/$A$3) | =A6:E6- $A$3:$E$3* (A6/$A$3) | |
Рис. 4. Формулы первого шага прямого хода исключения
Задание 3. Построить блок-схему алгоритма и разработать VBA-программу решения системы линейных уравнений методом Гаусса.
Задание 4. С помощью созданного рабочего листа Excel и разработанной VBA-программы решить системы уравнений методом Гаусса и вычислить выражения (согласно своему варианту):
1. Решить системы линейных уравнений АХ=В, А Х=В и вычислить значения квадратичной формы z=Y A A Y, где
, ,
2. Решить системы линейных уравнений АХ=В, А Х=В и вычислить значения квадратичной формы z=Y A A Y, где
, ,
3. Решить системы линейных уравнений АХ=В, А Х=В и вычислить значения квадратичной формы z=Y A A Y, где
, ,
4. Решить системы линейных уравнений АХ=В, А А Х=В и вычислить значения квадратичной формы z=Y А Y, где
, ,
5. Решить системы линейных уравнений АХ=В, А А Х=В и вычислить значения квадратичной формы z=Y А Y, где
, ,
6. Решить системы линейных уравнений АХ=В, А А Х=В и вычислить значения квадратичной формы z=Y А Y, где
, ,
7. Решить системы линейных уравнений АХ=В, АА АХ=В и вычислить значения квадратичной формы z=Y А А Y, где
, ,
8. Решить системы линейных уравнений АХ=В, АА АХ=В и вычислить значения квадратичной формы z=Y А А Y, где
, ,
9. Решить системы линейных уравнений АХ=В, АА АХ=В и вычислить значения квадратичной формы z=Y А А Y, где
, ,
10. Решить системы линейных уравнений АХ=В, А А АХ=В и вычислить значения квадратичной формы z=Y А А А Y, где
, ,
11. Решить системы линейных уравнений АХ=В, А А АХ=В и вычислить значения квадратичной формы z=Y А А А Y, где
, ,
12. Решить системы линейных уравнений АХ=В, А А АХ=В и вычислить значения квадратичной формы z=Y А А А Y, где
, ,
13. Решить системы линейных уравнений АХ=В, АА А Х=В и вычислить значения квадратичной формы z=Y А А Y, где
, ,
14. Решить системы линейных уравнений АХ=В, АА А Х=В и вычислить значения квадратичной формы z=Y А А Y, где
, ,
15. Решить системы линейных уравнений АХ=В, АА А Х=В и вычислить значения квадратичной формы z=Y А А Y, где
, ,
16. Решить системы линейных уравнений АХ=В, А А Х=В и вычислить значения квадратичной формы z=Y А А АY, где
, ,
17. Решить системы линейных уравнений АХ=В, А А Х=В и вычислить значения квадратичной формы z=Y А А АY, где
, ,
18. Решить системы линейных уравнений АХ=В, А А Х=В и вычислить значения квадратичной формы z=Y А А АY, где
, ,
19. Решить системы линейных уравнений АХ=В, А А Х=В и вычислить значения квадратичной формы z=Y А А А Y, где
, ,
20. Решить системы линейных уравнений АХ=В, А А Х=В и вычислить значения квадратичной формы z=Y А А А Y, где
, ,
21. Решить системы линейных уравнений АХ=В, А А Х=В и вычислить значения квадратичной формы z=Y А А А Y, где
, ,
22. Решить системы линейных уравнений АХ=В, АА А Х=В и вычислить значения квадратичной формы z=Y А А АY, где
, ,
23. Решить системы линейных уравнений АХ=В, АА А Х=В и вычислить значения квадратичной формы z=Y А А АY, где
, ,
24. Решить системы линейных уравнений АХ=В, АА А Х=В и вычислить значения квадратичной формы z=Y А А АY, где
, ,
25. Решить системы линейных уравнений АХ=В, АТААТХ=В и вычислить значение квадратичной формы z=YTAATAATY , где
26. Решить системы линейных уравнений АХ=В, АТААТХ=В и
вычислить значение квадратичной формы z=YTAATAATY , где
27. Решить системы линейных уравнений АХ=В, АТААТХ=В и
вычислить значение квадратичной формы z=YTAATAATY , где
28. Решить системы линейных уравнений АХ=В, АТААТХ=В и
вычислить значение квадратичной формы z=YTAATAATY , где
29. Решить системы линейных уравнений АХ=В, АТААТХ=В и
вычислить значение квадратичной формы z=YTAATAATY , где
30. Решить системы линейных уравнений АХ=В, АТААТХ=В и
вычислить значение квадратичной формы z=YTAATAATY , где
Задание 5. Построить блок-схему алгоритма и разработать VBA-программу поиска корня нелинейного уравнения f1(x)=f2(x) на заданном отрезке [a,b] c заданной точностью ε, реализовав в виде процедуры метод половинного деления. Используя процедуру решить уравнение приведенное таблице 1.
Задание 6. Подготовить рабочий лист в Excel для решения системы нелинейных уравнений методом Ньютона по следующему образцу (рис 4а) и решить уравнение в соответствии со своим вариантом. Значение погрешности e принять равным 0,001 для всех вариантов.
| Решение системы уравнений методом Ньютона | ||||||||
| Исходная система уравнений | Производные | |||||||
| f1=6x1^2+x2^2+10x1=0 | df1dx1=12x1+10 | df1dx2=2x2 | ||||||
| f2=2x1x2+2x2=0 | df2dx1=2x2 | df2dx2=2x1+2 | ||||||
| Шаг | x | f | W-якобиан | W-1-обратный | dx | |||
| df1 | df2 | |||||||
| x1 | 0,1 | 1,1 | 11,2 | 0,4 | 0,089869 | -0,01634 | 0,091667 | |
| x2 | 0,2 | 0,44 | 0,4 | 2,2 | -0,01634 | 0,457516 | 0,183333 | |
| x1 | 0,008333 | 0,084028 | 10,1 | 0,033333 | 0,099015 | -0,00164 | 0,008265 | |
| x2 | 0,016667 | 0,033611 | 0,033333 | 2,016667 | -0,00164 | 0,495895 | 0,01653 | |
| x1 | 6,83E-05 | 0,000683 | 10,00082 | 0,000273 | 0,099992 | -1,4E-05 | 6,83E-05 | |
| x2 | 0,000137 | 0,000273 | 0,000273 | 2,000137 | -1,4E-05 | 0,499966 | 0,000137 | |
| x1 | 4,67E-09 | 4,67E-08 | 1,87E-08 | 0,1 | -9,3E-10 | 4,67E-09 | ||
| x2 | 9,33E-09 | 1,87E-08 | 1,87E-08 | -9,3E-10 | 0,5 | 9,33E-09 |
Рис. 4а. Рабочий лист Excel для решения системы уравнений методом Ньютона.
Задание 7. Построить блок-схему алгоритма и разработать VBA-программу решения систем нелинейных уравнений методом Ньютона. С заданной точностью ε=0,001.
Задание 8. Преобразовать нелинейные уравнения системы из Таблицы 3а к виду f 1(x) = y и f 2 (y)= x. Построить их графики и определить начальное приближение решения. Затем решить с помощью метода Ньютона.
Таблица 3а. Задания к методу Ньютона