- •Министерство образования и науки Российской федерации
- •Кафедра математики и математических методов в экономике
- •ЧИСЛЕННЫЕ МЕТОДЫ
- •Хабаровск 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. Применение рядов в приближённом интегрировании
- •Оглавление
Пример 1. Пусть дана система
x2 y 2xz yz 2 1 03xyz 6 y 12 0
yx 3xz y2 3 0
Обозначим функции в левых частях системы соответственно как F, G, H . Найдём частные производные:
F |
2xy 2z, |
F |
x2 z2 , |
F |
2x 2 yz, |
|
|
x |
|
y |
|
|
z |
|
|
G |
3yz, |
G |
|
3xz 6, |
G |
3xy, |
|
x |
|
y |
|
|
z |
|
|
H |
y 3z, |
H |
|
x 2 y, |
H 3x. |
|
|
x |
|
|
y |
|
z |
|
|
Возьмём произвольную точку X 0 , |
|
например, |
X 0 0;1;2 , т.е. |
x 0, y 1, z 2 . |
Найдём значения функций в этой точке:
F 0;1;2 021 2 0 2 1 22 1 3;
G 0;1;2 3 0 1 2 6 1 12 6;
H 0;1;2 1 0 3 0 2 22 3 7,
и значения частных производных:
Fx 4, Fy 4, Fz 4, |
||
G |
6, G 6, F 0, |
|
|
|
|
x |
y |
z |
H |
5, H |
2, F 0. |
x |
y |
z |
Составим систему
4 x 4 y 4 z 3, |
|||||||||||
|
6 y |
0 z |
6 , |
||||||||
6 x |
|||||||||||
5 |
x |
2 |
y |
0 |
z |
7, |
|||||
|
|
|
|
|
|
|
|
|
|||
или, что равносильно, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y |
|
z |
0,75, |
|||||
|
|
x |
|
|
|
|
|
|
|||
|
x |
y 1, |
|
|
|||||||
|
|
5 |
|
2 |
|
7. |
|||||
|
|
x |
|
|
|
y |
|
|
|
||
|
|
|
|
|
|
|
|
Получаем x 9 / 7 1,28, y 2 / 7 0,28 , затем z 1,28 0,28 0,75 0,81 .
Новое приближение x 0 1,28 1,28, y 1 0,28 0,72 и z 2 0,81 2,81.
Первое приближение найдено, 1-й шаг закончен.
Чтобы решать задачу дальше, в новой точке надо найти значения функций и
частных производных так же, |
как находили |
их |
в точке |
X 0 , |
составить систему относительно |
x , y , z и |
решить, |
затем |
найти |
x 1,28 x , y 0,72 y , z 2,81 z , и т.д.
44
Вычисления прекращают, когда все i , где – необходимая точность вычислений, указанная заранее.
При решении задачи в пакете EXCEL для решения линейной системы проще всего воспользоваться функциями МОБР и МУМНОЖ. Выполнив 1-й шаг, можно разместить новое приближение в том же порядке, как начальное, и копировать формулы специальной вставкой, либо просто вручную заносить новое приближение на место прежнего. Однако число шагов для нелинейных систем может быть достаточно большим – до 10-15 и более приближений. Поэтому для систем 2-го порядка лучше формулы для вычисления 1 , 2 занести в явном виде, например, как формулы Крамера. А именно, для системы
Fx x Fy y F , Gx x G y y G
|
|
Fx |
Fy |
|
|
|
|
|
|
|
|
|
|
F |
|
Fy |
|
|
|
G F |
|
|
|
|||||||||||||
найти D |
F G |
y |
F |
G |
; |
|
D |
x |
|
|
FG |
y |
F |
G FG |
; |
|||||||||||||||||||||
|
|
|
Gx |
Gy |
x |
y |
x |
|
|
|
|
|
G |
|
Gy |
|
|
|
|
y |
|
|
|
|
|
y |
|
|
|
y |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Dy |
|
Fx |
F |
|
Fx G F |
Gx FGx FxG. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
Gx |
|
G |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Здесь D – определитель системы, |
Dx , Dy – вспомогательные определители, знак |
|||||||||||||||||||||||||||||||||||
производной опущен. Тогда согласно правилу Крамера |
|
|
|
D |
x |
и |
|
|
|
Dy |
|
. |
|
|||||||||||||||||||||||
x |
|
|
|
y |
D |
|
||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
D |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Пример 2. Решим с точностью 0,01 систему |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
xy 2x 3y 4 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 y 5x 6 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
Решение. Обозначим функции как F и G . Частные производные: |
|
|
|
|
||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
F y 2, F |
y |
x 3, G |
x |
2xy 5, G |
y |
x2 . |
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Возьмём произвольную точку, |
например, |
X 0 0;0 , т.е. пусть |
x 0 и |
y 0 . |
Выполним 2 шага подробно, а затем составим таблицу для вычислений. Поскольку точность 0,01 , действия выполняем с 3-мя знаками после запятой (3-я цифра запасная).
В точке X 0 0;0 значения функции |
F X 0 4, G X 0 6 , а значения произ- |
||||||||
водных |
F 0 2 2, F |
y |
0 3 3, G |
x |
0 5 5, G |
y |
02 |
0, |
соответствующая |
|
x |
|
|
|
|
|
линейная система имеет вид
45
|
2 x 3 y 4 |
|||||
|
|
5 |
x |
0 |
y |
6 , |
|
|
|
|
|
||
откуда x |
6 / 5 1,2 и y 4 2 1,2 / 3 0,533. |
|||||
Если же использовать приведённые выше общие формулы, то |
||||||
D 2 0 3 5 15, Dx 3 6 4 0 18 и Dy 4 5 2 6 8 , |
||||||
и тогда x |
18 /15 1,2 и y 8 /15 0,533 . |
|
|
|||
Новое приближение x 0 1,2 1,2 |
и y 0 0,533 0,533. Обозначим его как |
X 1 . В точке X 1 1,2; 0,533 значения функций
F X 1 1,2 0,533 2 1,2 3 0,533 4 0,640, G X 1 1,22 0,533 5 1,2 6 0,768 ,
а значения производных
Fx |
0,533 2 |
1,467, |
Fy |
1,2 3 1,8, |
|
|
|
|
|
|
|
|
|
||||||||||||
Gx |
2 1,2 0,533 5 |
6,279, |
|
Gy 1,22 1,44 . |
|
|
|
|
|
|
|
||||||||||||||
Соответствующая линейная система имеет вид |
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
1,467 x |
1,8 y |
0,640 |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
6,279 x |
1,44 y 0,678, |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
откуда x 0,251 и y 0,560. Новое приближение |
|
|
|
|
|||||||||||||||||||||
|
|
|
x 1,2 0,251 0,949 и y 0,533 0,560 1,093. |
||||||||||||||||||||||
Дальнейшие вычисления оформим в виде таблицы 2.3: |
|
|
|
|
|||||||||||||||||||||
Таблица 2.3 – Решение примера 2 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
строка |
|
x |
|
|
y |
|
|
|
F |
|
G |
|
Fx |
|
Fy |
|
Gx |
Gy |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
0 |
|
0 |
|
|
4 |
|
–6 |
|
–2 |
|
–3 |
|
5 |
|
0 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
2 |
|
1,2 |
|
0,533 |
|
0,64 |
|
0,678 |
–1,467 |
–1,8 |
6,279 |
1,44 |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
3 |
|
0,949 |
|
1,093 |
|
0,140 |
|
0,268 |
|
0,907 |
|
2,051 |
7,076 |
0,901 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
4 |
|
0,999 |
|
1,003 |
|
0,005 |
–0,006 |
|
0,997 |
|
2,001 |
7,003 |
0,997 |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
1 |
|
1 |
|
|
0 |
|
0 |
|
-1 |
|
-2 |
|
7 |
|
1 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Таблица 2.3 (окончание) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
строка |
|
D |
|
Dx |
|
Dy |
|
|
x |
|
|
y |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
1 |
|
|
|
15 |
|
18 |
|
8 |
|
1,2 |
|
0,533 |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
46 |
|
|
|
|
|
|
|
|
|
|
2 |
9,192 |
–2,304 |
5,146 |
–0,251 |
0,560 |
|
|
|
|
|
|
3 |
13,692 |
0,676 |
–1,236 |
0,049 |
0,090 |
|
|
|
|
|
|
4 |
13,021 |
0,016 |
0,037 |
0,001 |
–0,003 |
|
|
|
|
|
|
5 |
13 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
Здесь Dx , Dy и D найдены по указанным выше общим формулам. При при-
менении пакета Excel достаточно использовать ссылки на нужные значения
На 4-м шаге x 0,001 0,01 и y 0,003 0,01 , вычисления законче-
ны. Действительно, добавив эти величины к прежним значениям x, y , получаем x 1, y 1 , для которых F 0 и G 0 , а именно это нам и требуется. Попытка пересчитать x, y приводит к тем же самым значениям.
Ответ: с точностью 0,001 решение системы – x 1, y 1 .
Замечание 1. Из схемы следует, что для сходимости метода Ньютона нужно, чтобы ни на каком шаге решения определитель матрицы частных производных не обратился в 0.
Если определитель не обращается тождественно в 0 в каждой точке (тогда задачу вообще решить невозможно), то определить по первоначальному приближению, выполнено ли условие сходимости, весьма сложно, и этот вопрос выходит за рамки пособия. При решении в пакете Excel достаточно поменять начальное приближение.
Замечание 2. Также следует помнить, что, в отличие от линейных систем, нелинейная может иметь несколько решений, и небольшое изменение начального приближения может резко поменять ответ. Обычно это происходит, если начальное приближение находится вблизи стационарных точек системы.
Замечание 3. При решении упрощённым методом Ньютона можно не пересчитывать частные производные и использовать те, что получены на 1-м шаге (тогда матрица соответствующей системы относительно i не изменяется). Схо-
димость при этом может существенно замедлиться.
2.7. Поиск глобальных экстремумов функции и метод золотого сечения
Известно, что функция, непрерывная на отрезке, достигает на нём наименьшего и наибольшего значения либо на концах отрезка, либо в критических точ-
47
ках, где производная равна 0 или не существует. Отсюда следует простая схема поиска наименьшего и наибольшего значения функции f(x) на отрезке:
1) найти производную f x ;
2) найти с её помощью критические точки; 3) найти значения функции на концах отрезка и в критических точках, вхо-
дящих в отрезок; 4) выбрать самое большое и самое малое значения.
В этой схеме наиболее сложен 2-й пункт. По общей схеме можно найти корни только у простейших производных. В других случаях поиск критических точек возможен лишь приближённо, и точное решение всей задачи теряет смысл.
Эта же проблема возникает и при простом поиске экстремума по производной, поэтому необходимы способы поиска минимума и максимума, позволяющие обойтись без производной.
Поиск экстремума приближёнными методами похож на решение уравнения методом деления отрезка.
Пусть необходимо найти точку глобального минимума функции f(x) и известно, что она находится на отрезке [a, d]. Разделим отрезок на 3 части точками b, c так, чтобы a b c d и найдём значения f a , f b .
Пусть f b f c . Если функция не слишком «необычна», можно ожидать, что при движении слева к точке c функция возрастает. Тогда маловероятно, что точка минимума находится правее точки c, т.е. на участке [c, d], поэтому участок [c, d] можно исключить из рассмотрения. Скорее всего, точка минимума находится на промежутке [a, c], и именно на нём будем её искать дальше.
Наоборот, если f b f c , то, независимо от значений на концах отрезка, точка минимума должна быть на [b, d], но не на [a, b], и из рассмотрения можно исключить участок [a, b]. Скорее всего, на нём функция или всё время убывает, или возрастает до максимума и потом убывает.
В любом случае отсекая ненужный участок, получаем уменьшенный отрезок – либо [a, c], либо [b, d]. Переобозначив его как [a, d], снова делим на 3 части точками b, c и повторяем рассуждения.
Действуя так много раз, получим малый отрезок, длина которого будет меньше допустимой погрешности. Тогда любая точка такого отрезка может считаться точкой минимума (обычно берут середину отрезка).
Если же на отрезке [a, d] нет локального минимума, то произойдёт движение к концу отрезка, в котором значение функции меньше: к точке a, если
48