- •Министерство образования и науки Российской федерации
- •Кафедра математики и математических методов в экономике
- •ЧИСЛЕННЫЕ МЕТОДЫ
- •Хабаровск 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.2) с коэффициентами, являющимися решением системы (1.3),
называется интерполяционным многочленом (полиномом). Приближение при помощи многочлена Pn(x) называют параболическим интерполированием.
Проблема в том, что в системе (1.3) обычно получаются большие коэффициенты xk m из-за высоких степеней m n ; саму систему при большом числе урав-
нений сложно решать; при решении накапливаются ошибки, и окончательное решение неустойчиво. К тому же систему уравнений приходится заново составлять и решать при добавлении сведений об ещё одной точке или о не-
скольких точках.
Более экономичны такие способы построения полиномов, как метод множителей Лагранжа и метод разделённых разностей Ньютона.
1.2. Метод множителей Лагранжа
Идея метода – искать полином не в виде (1.2), а как
|
Ln x A0 0 x A1 1 x An n x , |
(1.4) |
где каждое k |
x x x j – произведение разностей аргумента со всеми точ- |
|
|
j k |
|
ками, кроме точки xk :
0 x x x1 x x2 x xn ,1 x x x0 x x2 x xn , и т.д.
Полином (1.4) выглядит громоздко, но при подстановке в него x0 получается
Ln x0 A0 0 x0 , а остальные слагаемые обращаются в 0. При подстановке x1 получим Ln x1 A1 1 x1 , и т.д., что позволяет быстро найти числа A0 , A1 , , An .
В подробной записи многочлен Ln(x) имеет вид:
Ln x y0 |
(x x1) (x xn ) |
|
y1 |
(x x1)(x x2 ) (x xn ) |
|
yn |
|
(x x0 )(x x1 ) (x xn 1 ) |
|
|
. (1.5) |
|||||||||||||||||||
(x |
0 |
x |
) (x |
0 |
x |
n |
) |
(x x |
0 |
)(x x |
2 |
) (x x |
n |
) |
(x |
n |
x |
)(x |
n |
x ) (x |
n |
x |
n 1 |
) |
|
|||||
|
|
1 |
|
|
|
|
1 |
1 |
|
1 |
|
|
|
0 |
|
1 |
|
|
|
|
||||||||||
Многочлен (1.5) называют интерполяционным многочленом Лагранжа. |
|
|||||||||||||||||||||||||||||
Приближённое равенство |
f x Ln x |
называют интерполяционной форму- |
||||||||||||||||||||||||||||
лой Лагранжа. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
При этом очевидны равенства
Ln x0 y0 , Ln x1 y1 , , Ln xk yk , , Ln xn yn ,
5
т.е. в узлах интерполяции xk значения многочлена (1.5) совпадают со значениями приближаемой функции f(x) , так как согласно таблице (1.1) выполняются равенства yk f xk .
Формула (1.5) значительно упростится в случае равноотстоящих узлов интер-
полирования, т.е. когда все отрезки |
|
[xk, xk+1] ( k 0,1,2, , n 1) будут одинаковой |
||||||||||||||||
длины h. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рассмотрим самую простую ситуацию, когда значения функции |
y f x за- |
|||||||||||||||||
даны в двух узлах интерполяции х0, |
х1: y0 |
f x0 , y1 f x1 . Тогда |
n 1 и со- |
|||||||||||||||
гласно (1.5) интерполяционный многочлен Лагранжа принимает вид |
|
|||||||||||||||||
L x y |
|
x x1 |
y |
x x0 |
. |
|
||||||||||||
|
|
|
|
|
||||||||||||||
1 |
|
|
|
0 |
x |
0 |
x |
1 |
x |
x |
0 |
|
|
|||||
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
|
|
|
|
||
Для функции f x получилось приближённое равенство |
|
|||||||||||||||||
f x y |
|
|
x x1 |
y |
|
x x0 |
|
|
|
(1.6) |
||||||||
0 |
|
x |
0 |
x |
1 x |
x |
0 |
|
|
|
||||||||
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
1 |
|
|
1 |
|
|
|
|
|
|
которое называют формулой линейной интерполяции, так как многочлен L1(x) есть линейная функция x kx b . При таком подходе дуга исходной интерполируемой кривой y f x на промежутке [x0, x1] заменяется отрезком прямой
y y |
|
x x1 |
y |
x x0 |
, |
(1.7) |
||
|
|
x |
x x |
|
||||
|
0 |
x |
1 |
0 |
|
|
||
|
|
0 |
1 |
|
1 |
|
|
соединяющим две точки (х0, у0) и (х1, у1) исходной таблицы (1.1). Так как х1≠х0, эти точки не являются вертикальными. Из аналитической геометрии известно, что уравнение прямой на плоскости, проходящей через точки (х0,у0) и (х1, у1), не являющиеся вертикальными, имеет вид
y y0 y1 y0 ( x x0 ) . x1 x0
Предлагаем читателю установить, что уравнение совпадает с последним. Учитывая сказанное, приближённое равенство (1.6) можно переписать в виде
f (x) f (x |
|
) |
y1 |
y0 |
(x x |
|
). |
(1.8) |
0 |
|
|
0 |
|||||
|
|
x1 |
x0 |
|
|
|||
|
|
|
|
|
|
Формула линейной интерполяции функции f(x) используется для приближённого вычисления её значений внутри промежутка [x0, x1].
В математическом анализе (точнее, дифференциальном исчислении функций одной переменной) для дифференцируемых функций хорошо известно другое приближённое равенство
f x f x0 f x0 x x0 , |
(1.9) |
6 |
|
применяемое для приближённого вычисления значений функции в окрестности ( x 0 ; x0 ) точки х0 достаточно малого радиуса .
Равенство (1.9) следует из определения производной в точке, т.е. из равенства
lim |
f ( x) f ( x0 ) |
f ( x ) |
|
||
x x0 |
0 |
|
x x0 |
или из приближённого равенства y(x0 ) dy(x0 ) для дифференцируемой функции, которое означает, что приращение функции в точке х0 ( y(x0 ) f (x) f (x0 ) )
примерно равно дифференциалу этой функции в точке х0 ( dy(x0 ) f (x0 ) x,x x x0 есть приращение аргумента). При этом точность последнего прибли-
жённого равенства тем больше, чем меньше x , т.е. чем ближе х к х0.
Так как справа в (1.9) стоит линейная функция, формулу (1.9) называют линеаризацией функции f(x) в окрестности точки х0. Эту формулу можно использовать как для x x0 , так и для x x0 , но достаточно близких аргументов х к х0.
Читателю рекомендуется дать геометрическую интерпретацию формулам
(1.8) и (1.9).
Схема построения полиномов Лагранжа
Шаг 1. Найдём коэффициенты k k xk :
|
0 x0 x1 x0 x2 x0 xn , |
|
|
1 x1 x0 x1 x2 x1 x3 x1 xn , |
|
|
2 x2 x0 x2 x1 x2 x3 x2 xn , |
|
и так до n |
xn x0 xn x1 xn |
x2 xn xn 1 . |
Каждый |
коэффициент k |
xk x j есть произведение разностей xk со |
|
|
j k |
всеми остальными значениями аргументов из таблицы (1.1).
Шаг 2. Пусть x – переменная. Составим произведение
x x x j x x0 x x1 x x2 x xn .
Полином Лагранжа для значений функции в точке x выглядит так:
|
y0 |
|
|
y1 |
|
|
|
|
y2 |
|
yn |
|
|||
Ln x ( x) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, |
|
x x0 |
1 |
x x1 |
|
2 |
x x2 |
|
||||||||
0 |
|
|
|
n x xn |
|||||||||||
где y0 , y1 , , yn – известные значения функции в точках |
x0 , x1 , , xn |
соответ- |
|||||||||||||
ственно. Последняя формула совпадает с (1.5). |
|
|
|
|
|
||||||||||
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
Шаг 3. Раскрывая внешние скобки, можно получить многочлен степени n
n |
|
|
x x |
|
y |
k |
|
|
x A |
x A |
x |
|
|
|
|
|
A |
||||||
|
|
|
|||||||||
|
|
j |
|
|
|
|
0 0 |
1 1 |
n n |
|
|
k 1 |
j k |
|
|
k |
|
|
|
|
как классический полином Лагранжа, а продолжая раскрытие скобок, свести к стандартному виду a0 a1x a2 x2 an xn , но обычно удобнее работать с поли-
номом в виде, полученном на шаге 2, хотя он и терпит устранимый разрыв во всех точках xk .
Пример. По таблице
х |
0 |
1 |
2 |
3 |
4 |
|
|
|
|
|
|
у |
2 |
3 |
6 |
11 |
18 |
|
|
|
|
|
|
построить полином Лагранжа и найти приближённые значения в точках 2,7 и 4,05. Решение. Удобно пронумеровать точки и значения:
x0 0, x1 1, x2 2, x3 3, x4 4 и y0 2, y1 3, y2 6, y3 11, y4 18.
Шаг 1. Находим коэффициенты
0 0 1 0 2 0 3 0 4 24 ,
1 1 0 1 2 1 3 1 4 6 ,2 2 0 2 1 2 3 2 4 4 ,
3 3 0 3 1 3 1 3 4 64 4 0 4 1 4 2 4 3 24 .
Шаг 2. Составим произведение x x 0 x 1 x 2 x 3 x 4 . Полином Лагранжа:
|
|
2 |
|
|
3 |
|
|
|
|
|
|
|
6 |
|
|
|
|
11 |
|
|
|
|
|
18 |
|
|||
L |
x x x 1 x 2 x 3 x 4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
4 |
|
24x |
|
|
6 x |
1 |
|
4 x 2 |
|
|
6 x 3 |
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
24 x 4 |
||||||||||||||||||||
или |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,0833 |
|
0,5 |
|
|
1,5 |
|
|
|
|
1,8333 |
|
|
0,75 |
|
|
||||||||||
|
L x x x 1 x 2 x 3 x 4 |
|
|
|
|
|
|
|
|
. |
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
4 |
|
|
|
|
|
x 1 |
|
|
x 2 |
|
|
x 3 |
|
|
|
|
|
|
|||||||||
|
|
|
x |
|
|
|
|
|
|
|
x 4 |
|
|
|||||||||||||||
Шаг 3. Раскрыв скобки, получим |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
L4 |
0,833 3 x 1 x 2 x 3 x 4 0,5x x 2 x 3 x 4 |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
1,5x x 1 x 3 x 4 1,833 3x x 1 x 2 x 4 0,75x x 1 x 2 x 3 . |
|
|||||||||||||||||||||||||||
|
|
|
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|