Численные методы
Число
(7)
називається
поділеною
різницею першого
порядку функції
(відповідно
точкам
).
Очевидно
(8)
тобто
поділена різниця
першого порядку
є симетричною
функцією аргументів
і
.
Поділена
різниця
-го
порядку
означається
через поділені
різниці
-го
порядку за
рекурентною
формулою
(9)
При обчисленнях поділені різниці записують у вигляді таблиці
Лема
2.
Поділена різниця
-го
порядку може
бути подана
через
вузлові значення
функції за
формулою
тобто є симетричною функцією своїх аргументів .
Доведення
.
При
твердження
леми виходить
з рівності
(8).
При
згідно з (9) маємо

Для
довільного
доведення
проводиться
за індукцією
.
Згідно
леми 2 значення
поділеної
різниці не
залежить від
порядку нумерації
вузлів, за якими
вона будується.
Всього маємо
варіантів
нумерації
вузлів цілими
числами від
0 до
.
Лема
3.
Якщо
тобто вузли
розміщуються
на осі з сталим
кроком
то між поділеною
різницею
-го
порядку та
скінченною
різницею
-го
порядку існує
наступний
зв’язок:
.
(12)
Доведення.
Для
=1
рівність (12)
виходить з (1),
(7). При довільному
доведення
провадиться
за індукцією.
При цьому
враховується
той факт, що
при визначенні
кожної наступної
за порядком
скінченної
різниці відбувається
згідно (3) віднімання
попередніх
різниць , а при
обчисленні
наступної
поділеної
різниці згідно
з формулою (9)
провадиться
додаткове
ділення на
величину
Звідси
й виникає величина
у
знаменнику
правої частини
рівності (12).
Лема
4.
Нехай
-мінімальний
відрізок, що
містить вузли
.
Тоді існує така
точка
![]()
що
.
(13)
Доведення . Для вузлів, що розміщені з сталим кроком, рівність (13) безпосередньо виходить з лем 1, 3.
Доведення
у загальному
випадку можна
здійснити
наступним
чином. Візьмемо
точку
та побудуємо
поділену різницю
-го
порядку
З
цього виразу
можна одержати

Співставляючи останнє з раніш одержаним виразом для похибки
,
одержуємо

Покладаючи
тепер
,
одержимо (13).
Висновок
з леми 4.
Поділена різниця
-го
порядку від
алгебраічного
многочлена
-го
ступеню має
стале значення,
що не залежить
від вузлів
а поділені
різниці ще
вищих порядків
дорівнюють
нулеві.
Скінченні і поділені різниці мають різноманітні застосування. Далі розглянемо їх використання для побудови інтерполяційних многочленів.
Інтерполяційний многочлен Ньютона .
Нехай
-довільні
вузли, що не
співпадають
і у яких відомі
значення функції
.
Лема
1. Алгебраїчний
многочлен
-го
ступеню
є
інтерполяційним,
тобто
(2)
Доведення.
Поперш за все
зауважимо,що
поділені різниці
є числа (не залежать
від
), і тому функція
(1) дійсно є алгебраїчний
многочлен
-го
ступеню. Доведемо
(2) при
.
Маємо ![]()
Очевидно
,

Тобто
при n=1
рівності
(2) справедливі.
Доведемо
(2) при
.
Маємо
![]()
![]()
![]()

При
рівності (2)
доведені .
При
довільному
натуральному
рівності (2)
доводяться
за індукцією.
Многочлен (1) називається інтерполяційним многочленом Ньютона для нерівних проміжків .
Згідно
теоремі єдності
він тотожньо
співпадає з
інтерполяційним
многочленом
Лагранжа, тобто
Таким чином
ми маємо різні
записи інтерполяційного
многочлена.Залишковий
член інтерполяційного
многочлена
Ньютона той
же, що і інтерполяційного
многочлена
Лагранжа, тобто
всюди в оціночних
рівностях і
нерівностях
можна замінити
на
![]()
У
інтерполяційного
многочлена
Лагранжа видно
його явну залежність
від кожного
значення функції
Це у багатьох
випадках буває
корисним. Але
при зміні
інтерполяційний
многочлен
Лагранжа треба
будувати заново.
У цьому є його
недолік.
Інтерполяційний
многочлен
Лагранжа (1) містить
не значення
функції
,
а її поділені
різниці. При
зміні степеню
у інтерполяційного
многочлена
Ньютона треба
добавити або
відкинути
відповідну
кількість
стандартних
доданків. Це
зручно на практиці.
Випадок
равновіддалених
вузлів.
Нехай
![]()
Тоді,
враховуючи
зв’язок
поділеної
різниці із
скінченною
різницею

і вводячи безрозмірну змінну

інтерполяційний многочлен (1) можна переписати у вигляді
Цей многочлен називається інтерполяційним многочленом Ньютона для інтерполяції вперед.
У
ньому початок
відліку знаходиться
у крайньому
вузлі
,
а використані
скінченні
різниці йдуть
у таблиці різниць
від
вправо униз.
Інтерполяційний
многочлен (3)
зручно використовувати
на початку
таблиці.
Інтерполяційний
многочлен
з
вулами
,
,де
,
має вигляд
(4)
і називається інтерполяційним многочленом Ньютона для інтерполяції назад.
У
ньому початок
відліку
розташований
у крайньому
правому вузлі
,
а вікористані
скінченні
різниці йдуть
у таблиці від
вправо угору
.

Інтерполяційний многочлен (4) зручно використовувати при інтерполяції у кінці таблиці.
Якщо
при заданому
у таблиці значень
функції
з кроком
![]()
маємо
достатню кількість
вузлів з кожного
боку від
,
то доцільно
вузли інтерполяції
вибирати так,
щоб точка
опинилась як
можна ближче
до середини
мінімального
відрізку, що
містить вузли.
При цьому
інтерполяційний
многочлен можна
будувати по-
різному.
Найбільш
істотньо задати
інтерполяційний
многочлен у
вигляді (1), де
за
береться найближчий
до
вузол, далі за
приймається
найближчий
до
вузол, що міститься
з протилежного
від
боку, ніж
.
Наступні вузли
призначаються
по черзі з різних
боків від
,
що містяться
як можливо
ближче до
.
При токому
виборі вузлів
доданки, що
слідують один
за одним у виразі
(1), як правило,
спадають, якщо
мале, а
невелике.
Можливо також у розглянутому випадку використовувати інтерполяційні многочлени (3), (4), а також інтерполяційний многочлен Лагранжа.
На закінчення зазначимо, що залишковий член многочлена (3) має той же вигляд, що і у випадку інтерполяційного многочлена Лагранжа з рівновіддаленими вуздами, тобто
а
залишковий
член інтерполяційного
многочлена
(4) може бути подано
у вигляді
де
-похідна від
,
-деяка
точка мінімального
відрізку, що
містить вузли
інтерполяції
і точку
.
Згідно
лемі, у якій
показано, що
та при умові,
що
мале, а функція
достатньо
гладка, поточний
доданок у виразі
(3) інтерполяційного
многочлена
Ньютона приблизно
дорівнює похибці
інтерполяції
многочленом,
побудованим
з усіх попередніх
доданків. Це
зауваження
стосується
й до інтерполяційного
многочлена
(4) для інтерполяції
назад.
МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА.
Основная идея метода. Может оказаться, что система
Ax=f (1)
имеет единственное решение, хотя какой-либо из угловых миноров матрицы А равен нулю. В этом случае обычный метод Гаусса оказывается непригодным, но может быть применен метод Гаусса с выбором главного элемента.
Основная
идея метода
состоит в том,
чтобы на очередном
шаге исключать
не следующее
по номеру
неизвестное,
а то
неизвестное,
коэффициент
при котором
является наибольшим
по модулю. Таким
образом, в качестве
ведущего элемента
здесь выбирается
главный,
т.е. наибольший
по модулю элемент.
Тем самым, если
,
то в процессе
вычислений
не будет происходить
деление на
нуль.
Различные варианты метода Гаусса с выбором главного элемента проиллюстрируем на примере системы из двух уравнений
(2)
![]()
![]()
![]()
Предположим,
что
.
Тогда на первом
шаге будем
исключать
переменное
.
Такой прием
эквивалентен
тому, что система
(2) переписывается
в виде
(3)
![]()
и к (3) применяется первый шаг обычного метода Гаусса. Указанный способ исключения называется методом Гаусса с выбором главного элемента по строке. Он эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация переменных.
Применяется
также метод
Гаусса с выбором
главного элемента
по столбцу.
Предположим,
что
.
Перепишем
систему (2) в
виде
![]()
и к новой системе применим на первом шаге обычный метод Гаусса. Таким образом, метод Гаусса с выбором главного элемента по столбцу эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация уравнений.
Иногда применяется и метод Гаусса с выбором главного элемента по всей матрице, когда в качестве ведущего выбирается максимальный по модулю элемент среди всех элементов матрицы системы.
Матрицы перестановок. Ранее было показано, что обычный метод Гаусса можно записать в виде
![]()
где
-элементарные
нижние треугольные
матрицы. Чтобы
получить аналогичную
запись метода
Гаусса с выбором
главного элемента,
необходимо
рассмотреть
матрицы перестановок.
ОПРЕДЕЛЕНИЕ 1. Матрицей перестановок Р называется квадратная матрица, у которой в каждой строке и в каждом столбце только один элемент отличен от нуля и равен единице.
ОПРЕДЕЛЕНИЕ
2.
Элементарной
матрицей перестановок
называется
матрица, полученная
из единичной
матрицы перестановкой
к-й
и l-й
строк.
Например, элементарными матрицами перестановок третьего порядка являются матрицы
Можно отметить следующие свойства элементарных матриц перестановок, вытекающие непосредственно из их определения .
Произведение двух (а следовательно, и любого числа) элементарных матриц перестановок является матрицей перестановок (не обязательно элементарной).
Для любой квадратной матрицы А матрица
отличается
от А
перестановкой
к-й
и
l-й
строк.Для любой квадратной матрицы А матрица
отличается
от А
перестановкой
к-го
и l-го
столбцов.
Применение элементарных матриц перестановок для описания метода Гаусса с выбором главного элемента по столбцу можно пояснить на следующем примере системы третьего порядка: