- •Министерство образования и науки Российской федерации
- •Кафедра математики и математических методов в экономике
- •ЧИСЛЕННЫЕ МЕТОДЫ
- •Хабаровск 2014
- •1.1. Постановка задачи о приближении функций
- •1.2. Метод множителей Лагранжа
- •Идея метода – искать полином не в виде (1.2), а как
- •Схема построения полиномов Лагранжа
- •Шаг 2. Пусть x – переменная. Составим произведение
- •Шаг 3. Раскрывая внешние скобки, можно получить многочлен степени n
- •Пример. По таблице
- •Шаг 1. Находим коэффициенты
- •Шаг 3. Раскрыв скобки, получим
- •1.3. Метод разделённых разностей и полиномы Ньютона
- •Часть 1. Разностные аналоги производных
- •Часть 2. Рекурсивное вычисление функции
- •Пример. Известна таблица значений функции
- •Ответ: значения полинома Ньютона равны 18 в точке 2 и 2,2401 в точке 0,7.
- •Аналогично
- •Продифференцировав каждое слагаемое три раза, получим
- •1.5. Метод наименьших квадратов
- •Поиск линейной зависимости
- •Подставив суммы в систему (1.11), получим
- •Подставив найденные суммы в систему (1.12), получим
- •Пример 4. По приведённым данным
- •Отсюда очевидным образом имеем, что
- •Схема метода касательных
- •Вычисление корней при помощи метода простых итераций
- •Составим систему
- •Соответствующая линейная система имеет вид
- •Таблица 2.3 – Решение примера 2
- •Общая схема метода
- •Остаётся сравнить значения
- •Общая схема метода золотого сечения
- •Пусть функция f(x) задана таблицей
- •Проинтегрировав, получаем, что
- •Последовательно находим
- •Интегрируя каждое слагаемое, получим, что
- •Тогда интеграл сводится к
- •Проинтегрировав каждое слагаемое, получим
- •По теореме об интегрировании сходящихся степенных рядов
- •Если интеграл определённый, то
- •Найдём значения
- •По формуле трапеций получим
- •По формуле Симпсона будет
- •По формуле парабол
- •Поскольку значения на концах не зависят от числа точек и
- •Ответ:
- •Шаг 4. Ответ:
- •Тогда
- •Ответ:
- •Ответ:
- •Формула метода 3-го порядка точности:
- •Ответ:
- •Формула метода 4-го порядка точности
- •Все дальнейшие вычисления аналогичны и приведены в таблице.
- •Таблица (начало)
- •Таблица (окончание)
- •Ответ:
- •Пример 1. Решим систему
- •Ответ:
- •Последнее преобразуется к виду
- •Задачу (5.10) – (5.11) будем записывать в виде операторного уравнения
- •Из ограниченности третьей производной следует, что
- •Таким образом, точность близости будет О(h).
- •В силу граничных условий имеет место и неравенство
- •Если yh есть решение уравнения (5.12), то из (5.27) имеем оценку
- •Замечание о делении отрезка на части
- •Решение уравнений делением отрезка
- •Метод секущих (хорд)
- •При реализации в EXCEL достаточно заполнить строчку
- •Метод касательных
- •Реализация метода мало отличается от метода секущих, заполняем строку
- •Таблица 6.1 – Решение уравнения
- •Подбор полиномов, проходящих через точки
- •Таблица 6.2 – Поиск полинома при помощи обратной матрицы
- •Полиномы Лагранжа
- •Таблица 6.3 – Построение полинома Лагранжа
- •Таблица 6.4 – Построение полинома Ньютона
- •Метод Эйлера решения задачи Коши
- •Таблица 6.5 – Решение уравнения методом Эйлера
- •Приближённое интегрирование
- •Таблица 6.6 – Вычисление интеграла методом трапеций и методом Симпсона
- •ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
- •Часть 1. Задания для работы без пакетов прикладных программ
- •Задание 1. Решение уравнений
- •Задание 2. Метод простых итераций
- •Задание 3. Метод простых итераций в приближённых вычислениях
- •Задание 4. Полиномы Лагранжа и Ньютона
- •Задание 5. Метод наименьших квадратов
- •Задание 6. Приближённое интегрирование
- •Задание 7. Задача Коши
- •Часть 2. Задания для работы в пакете EXCEL
- •Задание 1. Приближение функций полиномами
- •Задание 2. Задача Коши
- •Задание 3. Системы дифференциальных уравнений
- •Задание 4. Задача Коши 2-го порядка
- •Задание 5. Приближённое интегрирование
- •Задание 7. Метод Ньютона решения систем нелинейных уравнений
- •Задание 9. Применение рядов в приближённом интегрировании
- •Оглавление
3) Найти несколько элементов последовательности xn по одной из формул п. 1.
4) Если сходимость «просматривается», увеличить m и продолжить п. 3.
5)Если сходимости нет, найти несколько элементов по другой формуле п. 1.
6)Если сходимости снова нет, поменять x0 и повторять пункты 3-5, пока ре-
шение не начнёт получаться.
Замечание о скорости сходимости. При замене уравнения f x 0 на равно-
сильное x g x не так очевидно, достигнута ли нужная точность, поскольку при малом m приближения xn 1 и xn мало отличаются, а значение функции f(x)
по значению функции g(x) неясно. Доказано, что для возрастающих функций f(x) всегда
c xn |
|
|
|
q |
|
xn 1 |
xn |
|
, |
|
|
|
|
||||||
|
|
|
|
|
|||||
|
|
q |
|||||||
|
|
1 |
|
|
|
|
|
а для убывающих f(x) всегда c xn xn 1 xn , что позволяет по разности между двумя приближениями оценить настоящий корень уравнения.
|
|
Таким образом, если уравнение f x 0 |
|
надо решить с точностью , то есть |
|||||||||||||||||||||||||
прийти к выполнению условия |
|
c xn |
|
, в случае возрастающей f |
надо прово- |
||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||
дить |
пересчёт, пока не получится |
|
q |
|
x |
n 1 |
x |
n |
|
, или, что то |
же самое, |
||||||||||||||||||
|
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|||||||||||||||||||||||||
1 q |
|||||||||||||||||||||||||||||
|
x |
n 1 |
x |
n |
|
|
1 q |
. |
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
q |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
Когда это произойдёт, можно утверждать, что с точностью корень c xn . |
|||||||||||||||||||||||||||
|
|
Если оценить параметр q затруднительно, то, заметив, что xn 1 xn , следу- |
|||||||||||||||||||||||||||
ет найти |
f xn 1 , и если окажется, что |
f xn 1 , вычисления можно прекратить. |
|||||||||||||||||||||||||||
|
|
Из формул для оценки решения следует, что при q 1 знаменатель 1–q бли- |
|||||||||||||||||||||||||||
зок к 0, дробь велика, и оценить |
|
c xn |
|
нельзя. Наоборот, при q 0 дробь мала, и |
|||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||
тогда |
|
c xn |
|
0 , то есть xn c . |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Вычисление корней при помощи метода простых итераций
39
Известная формула x2 x 1 позволяет с какой угодно точностью извлекать корни любой целой степени из любого положительного числа.
Пусть надо найти |
|
|
A |
|
или, что тоже самое, |
решить уравнение x2 A при |
|||||||||||||||
x 0 . Заметим, |
что тогда |
x2 1 A 1 , то есть x 1 x 1 A 1. Отсюда можно |
|||||||||||||||||||
получить x 1 |
|
A 1 |
и одновременно x 1 |
A 1 |
|
. Производные правых частей |
|||||||||||||||
|
x 1 |
|
x 1 |
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
A 1 |
|
A 1 |
|
1 |
A 1 |
|
|
A 1 |
|
|||||||||
соответственно |
1 |
|
|
|
|
|
|
и |
|
|
|
|
|
. |
|||||||
|
|
|
|
x 1 2 |
|
|
|
x 1 2 |
|||||||||||||
|
|
|
x |
1 |
|
|
|
x 1 |
|
|
|
Поскольку при x 0 |
|
всегда x 1 2 |
x 1 2 , в 1-м случае производная меньше |
||||||||||||||||||||||||||
(по модулю) и результат получается быстрее. |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
Выбираем |
любое x0 0 , чтобы |
|
выполнялось |
x0 1 2 |
A 1. Находим |
1-е |
|||||||||||||||||||||||
приближение |
x 1 |
A 1 |
|
и затем все следующие как x |
|
|
1 |
|
A 1 |
. |
|
||||||||||||||||||
|
|
|
1 |
x0 |
1 |
|
|
|
|
|
|
|
|
|
n 1 |
|
|
|
|
xn 1 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Последовательность xn |
A . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Пример 1. Найдём |
6 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
Решение. |
Итерационная формула имеет вид xn 1 |
1 |
|
|
5 |
|
. Подберём x0 |
, |
|||||||||||||||||||||
|
|
|
|
||||||||||||||||||||||||||
xn |
1 |
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
чтобы x0 1 2 |
5 . Например, подходит x0 |
2 . Находим |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
x1 1 |
|
5 |
|
2,666 7 |
; x2 1 |
|
|
5 |
|
2,363 5 ; |
x3 1 |
|
|
5 |
|
2,486 5 |
; |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
2,363 5 1 |
||||||||||||||||||||||
2 |
1 |
|
|
|
|
|
|
|
|
2,666 7 1 |
|
|
|
|
|
|
|
и далее таким же образом последовательность
2,434 1, 2,456 0, 2,446 8, 2,450 6, 2,449 0, 2,449 7, 2,449 4, 2,449 5.
Вычисления ведём с 4-мя знаками и прекращаем, когда числа повторяются.
Ответ: 6 2,449 5 .
Подобным образом можно найти 3 A .
Заменив уравнение x3 A на равносильное ему x 1 x2 x 1 A 1 , полу-
чаем последовательность xn 1 1 |
|
A 1 |
|||||
|
|
|
|
|
. |
|
|
x2 |
x |
|
1 |
||||
|
n |
|
|
n |
|
|
|
Модуль производной правой части |
A 1 2x 1 |
заведомо меньше 1 при до- |
x2 x 1 2
статочно больших значениях x.
40
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Пример 2. Найдём 3 10 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Решение. |
Преобразовав |
уравнение |
x3 |
|
10 к |
виду |
x 1 x2 x 1 10 1 , |
|||||||||||||||||||
получаем итерационную формулу xn 1 1 |
|
9 |
|
|
. |
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
x2 x |
|
1 |
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
n |
|
|
|
|
|
|
|
|
|
|||
При x0 4 модуль производной |
9 2 4 1 |
|
|
|
|
81 |
|
1 . Приближение допустимо, и |
||||||||||||||||||
42 4 1 2 |
|
|
441 |
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
x1 1 |
|
9 |
|
1,429 ; x2 1 |
|
9 |
|
|
|
|
|
3,013 |
; x |
|
1 |
|
9 |
|
1,687. |
|||||||
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
2 |
|
|
||||||||||||||
42 |
4 1 |
1,4292 1,429 1 |
|
|
|
|
|
3,013 1 |
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3,013 |
|
Продолжая, получаем последовательность 2,626, 1,855, 2,429, 1,906, 2,377, и с некоторого момента чередуются числа 2,154 и 2,155.
Ответ: 3 10 2,155 .
Пример 3. Посмотрим, что произойдёт, если при поиске 3 64 взять x0 4 –
точный корень.
|
Решение. Итерационная формула имеет вид xn 1 |
1 |
|
63 |
|
. |
|||||||||||||||||
|
|
|
|
||||||||||||||||||||
|
x2 x |
|
1 |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
n |
|
|
|
|
Если |
x |
|
4 , то x |
1 |
|
63 |
|
1 |
63 |
4 , результат не изменяется. |
||||||||||||
|
0 |
|
|
|
|
||||||||||||||||||
|
|
|
|
|
1 |
42 |
4 1 |
21 |
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
Замечание. Уравнение |
x2 |
A |
при |
любом |
b |
равносильно уравнению |
||||||||||||||||
x b x b A b2 , |
и можно |
составлять |
итерационные |
последовательности |
|||||||||||||||||||
x |
|
b |
A b2 |
. Это ускоряет сходимость при малых |
A b2 |
0 . Подобное спра- |
|||||||||||||||||
n 1 |
xn |
b |
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ведливо и для уравнений xk A .
2.6. Решение систем нелинейных уравнений методом Ньютона
Пусть дана система n нелинейных функциональных уравнений относительно n переменных x1 , x2 , , xn :
f1 x1 , x2 , , xn 0,f2 x1 , x2 , , xn 0,
fn x1 , x2 , , xn 0,
41
где fi x1 , x2 , , xn 0 при i 1,2, , n – некоторые известные функции. Набор переменных x1 , x2 , , xn служит решением системы, если отвечает каждому её уравнению. Точно решить такие системы можно лишь в простейших случаях. Единственно возможный общий метод – метод подстановки, когда переменные выражаются через остальные и система сводится к одному уравнению исключением переменных, здесь не подходит, поскольку в лучшем случае получится очень громоздкое уравнение, а в большинстве случаев такое исключение само невозможно.
Метод Ньютона – один из основных приближённых методов решения таких систем. Он основан на следующих идеях:
1) для дифференцируемой функции одной переменной справедливо приближённое равенство f (x) f x0 f x0 x x0 , где x0 – произвольная точка, а x x0
;
2) поскольку наша цель – подобрать x так, чтобы f x 0 , а значения f x0 и f x0 известны, получается линейное уравнение относительно x x0 или, что равносильно, относительно x ;
3) аналогичное равенство справедливо и для функции многих переменных,
если точки |
x |
0 |
и x |
заменить векторами X 0 x0 |
, x0 |
, , x0 |
и |
X x , x |
2 |
, , x |
n |
, |
|
|
|
1 |
2 |
n |
|
1 |
|
|
|||
производную заменить вектором частных производных, а произведение |
f X 0 и |
X X 0 считать скалярным;
4) в случае многих переменных получается линейное уравнение относительно X X 0 , содержащее n неизвестных x1 , x2 , , xn ;
5)для однозначного поиска n неизвестных в общем случае достаточны n независимых уравнений, и каждое такое уравнение получается дифференцированием очередной функции f2 , f3 , , fn ;
6)таким образом, получается система n линейных уравнений относительно n неизвестных x1 , x2 , , xn , решить которую можно известными способами либо
точно, либо приближённо.
Запишем систему в общем виде. Пусть X 0 x10 , x20 , , xn0 – некоторое началь-
ное приближение, X x1 , x2 , , xn – некоторая точка, близкая к X 0 . Тогда можно считать, что
42
f |
|
x ; x |
|
; x |
|
|
f |
|
|
|
f1 |
|
x x0 |
f1 |
|
|||||
1 |
|
n |
1 |
|
|
|||||||||||||||
|
1 |
2 |
|
|
|
|
x1 |
1 |
1 |
x2 |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
f |
|
|
x1 |
x10 |
f |
|
|
|
|
|
x1; x2 ; xn |
f2 |
|
2 |
2 |
|
|||||||||||||
f |
2 |
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
|
|
x2 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
fn |
x x0 fn |
|||||||
f |
n |
x ; x |
2 |
; x |
n |
f |
n |
|||||||||||||
|
1 |
|
|
|
|
|
|
x1 |
1 |
1 |
x2 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
x0 |
f1 |
|
x |
|
|
x0 , |
|||||
2 |
|
|
|
n |
||||||||||
|
2 |
|
xn |
|
|
n |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
||||
x |
|
x0 |
|
|
f2 |
|
x |
|
x0 |
, |
||||
2 |
|
|
n |
|||||||||||
|
|
2 |
|
|
|
xn |
|
|
|
n |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
x |
|
x0 |
|
fn |
|
x |
|
x0 |
. |
|||||
2 |
|
|
n |
|||||||||||
|
|
2 |
|
|
|
xn |
|
|
|
n |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
Здесь все значения функций и частных производных в правой части найдены
в точке X 0 . |
|
|
|
|
|
|
|
|
|
|
|
Предположим, |
что точка X x1 , x2 , , xn одновременно оказалась решением |
||||||||||
исходной системы, |
тогда |
fi x1, x2 , , xn 0 для |
i 1,2, , n . В новой системе |
||||||||
также |
получим 0 |
слева |
в |
каждом уравнении. |
Обозначим для краткости |
||||||
1 x1 |
x10 , 2 x2 |
x20 , , n |
xn xn0 , перенесём |
f |
, f |
2 |
, , f |
n |
и переставим части |
||
|
|
|
|
|
|
1 |
|
|
|
уравнений слева направо, получим систему относительно 1 , 2 , , n в виде
f1 1 f1x1 x2f 2 f 2
x1 1 x2
f n 1 f nx1 x2
2 f1 n f1,
xn
2 f 2 n f 2 ,
xn
2 f n n f n ,
xn
где по-прежнему все функции и частные производные подсчитаны в точке X 0 .
Найдя все i , можно найти и все xi xi0 i xi xi0 i .
Если бы все функции fi были линейны по каждому аргументу, система совпала бы с исходной, и точка X действительно оказалась бы решением обеих систем. Но тогда была бы неактуальна сама задача. Для нелинейных же систем точка X , полученная как решение последней системы, в большинстве случаев окажется ближе к решению исходной системы, чем точка X 0 . Тогда, обозначив X как X 0 , можно заново проделать все действия, ещё более приблизиться к решению, и продолжать так, пока приближения не станут совпадать с необходимой точностью.
Существенно, что общие формулы частных производных не меняются от шага к шагу, и задачу можно легко запрограммировать. Покажем один шаг решения методом Ньютона.
43