Материал из eSyr's wiki.

Версия 16:07, 8 июня 2010 (править) 217.197.227.54 (Обсуждение) (→Погрешность инторполяционной формулы Ньютона) ← К предыдущему изменению		Версия 16:08, 8 июня 2010 (править) (отменить) 217.197.227.54 (Обсуждение) (→Погрешность инторполяционной формулы Ньютона) К следующему изменению →
Строка 422:		Строка 422:
	== Когда лучше использовать Ньютона, а когда — Лагранжа		== Когда лучше использовать Ньютона, а когда — Лагранжа
-	* Ньютон удобен при постепенном добавлении узлов, когда их количество нефиксировано	+	* Ньютон удобен при постепенном добавлении узлов, когда их количество не фиксировано
	* Лагранж удобен, когда количество узлов фиксировано, но они могут находиться в разных местах		* Лагранж удобен, когда количество узлов фиксировано, но они могут находиться в разных местах

---

Версия 16:08, 8 июня 2010

Содержание 1 Глава 1 1.1 Система линейных алгебраических уравнений (СЛАУ) 1.2 Группы методов решения СЛАУ 1.3 Прямой метод решения СЛАУ 1.4 Задача на собственные значения 1.5 Факторизация матрицы 1.6 В каком порядке ищутся элементы матриц B и C при факторизации А = B × C 1.7 Условие существования и единственности разложения А = B × C 1.8 Связь метода Гаусса с разложением A = B × C 1.9 Метод Гаусса-Жордана 1.10 Метод квадратного корня (метод Холецкого) 1.11 Достоинства и недостатки метода квадратного корня 1.12 Что значит «решить СЛАУ итерационным методом» 1.13 Вопросы, рассматриваемые при исследовании итерационного метода 1.14 Метод Якоби 1.15 Достоинства и недостатки метода Якоби 1.16 Метод Зейделя 1.17 Соотношение сложностей методов Якоби и Зейделя 1.18 Двуслойная запись 1.19 Каноническая форма записи двуслойного итерационного метода решения СЛАУ 1.20 Виды итерационных методов 1.21 Метод простой итерации 1.22 Попеременно-треугольный итерационный метод (метод Самарского) (ПТИМ) 1.23 Невязка 1.24 Энергетическая норма 1.25 Вектор погрешности 1.26 Матрица перехода 1.27 Условие сходимости матрицы при любом начальном приближении, условие на матрицу перехода 1.28 Достаточное условие сходимости итерационного метода (теорема Самарского) 1.29 Теорема о сходимости метода Якоби 1.30 Теорема о сходимости метода простой итерации 1.31 Теорема о сходимости метода Зейделя 1.32 Скорость сходимости итерационного метода 1.33 Оценка скорости сходимости итерационного метода 1.34 Равенство Парсеваля 1.35 Оценка скорости сходимости МПИ 1.36 Теорема о сходимости ПТИМ 1.37 Теорема об оценке скорости сходимости ПТИМ 1.38 Оценка скорости сходимости для метода простой итерации 1.39 Задача на собственные значения 1.40 Степенной метод нахождения собственных значений 1.41 Условия для степенного метода 1.42 Метод обратных итераций 1.43 Метод обратных итераций со сдигом 1.44 Что такое верхняя почти треугольная форма 1.45 Преобразование элементарных отражений (преобразование Хаусхолдера) 1.46 QR-алгоритм решения полной проблемы собственных значений 1.47 Количество действий для работы QR-алгоритма 1.48 Теорема о сохранении ВПТФ 2 Глава 2 2.1 Задача интерполяции 2.2 Интерполяционный полином 2.3 Существование и единственность интерполяционного полинома 2.4 Интерполяционный полином в форме Лагранжа 2.5 Определение погрешности интерполяционного полинома 2.6 Разделённая разность 2.7 Выражение разделённой разности через значения функции в точках 2.8 Выражение разделённой разности через значение функции в 0-м узле и разделённую разность k-го порядка 2.9 Интерполяционная функция в форме Ньютона 2.10 Погрешность инторполяционной формулы Ньютона 2.11 Интерполяционная формула Эрмита 2.12 Общий вид полинома Эрмита 2.13 H3(x) 2.14 Погрешность полинома Эрмита 2.15 Формула Симпсона 2.16 Оценка погрешности формулы Симпсона 2.17 L2 для функций 2.18 Наилучшее среднеквадратичное приближение 2.19 Отклонение 3 Глава 3 3.1 Нелинейная система 3.2 Задачи связанные с решением нелинейных уравнений и систем 3.3 Метод бисекции решения нелинейного уравнения 3.4 Метод простой итерации (МПИ) 3.5 Условие наличия корня в отрезке при использовании МПИ 3.6 Специальный вид МПИ 3.7 Границы выбора τ для МПИ, записанного в специальном виде для сходимость со скоростью геометрической прогрессии 3.8 Метод Эйткена 3.9 Метод Ньютона (касательных) 3.10 Модифицированный метод Ньютона 3.11 Метод Ньютона для системы из 2 уравнений 3.12 Метод Ньютона: общий случай для m уравнений 3.13 Метод секущей (хорд) 3.14 Комбинированный метод 3.15 Скорость сходимости метода Ньютона 3.16 Скорость сходимости модифицированного метода Ньютона

Глава 1

Система линейных алгебраических уравнений (СЛАУ)

Система линейных алгебраических уравнений:

• Ax = f
• A (m × m), det A ≠ 0 — решение есть, оно единственное
• x = (x₁, x₂, ... x_m)^T
• f = (f₁, f₂, ... f_m)^T

Группы методов решения СЛАУ

К курсе рассматриваются две группы методов:

1. Прямые (точные) методы
2. Итерационные (приближённые) методы

Прямой метод решения СЛАУ

Прямой метод решения СЛАУ — метод, который позволяет реализовать в алгоритме определённые формулы, то есть аналитическое решение.

Задача на собственные значения

Задача на собственные значения — задача о нахождении такого числа λ, что Ax = λ × x, x ≠ 0 — собственный вектор, λ — собственное значение.

Факторизация матрицы

Факторизация матрицы — представление матрицы А в виде произведения B × C, где

B — нижнетреугольная матрица: b11 0 0 ... 0 b21 b22 0 ... 0 ... b1m b2m b3m ... bmm

C — верхнетреугольная матрица с единицами на диаонали: 1 c12 c13 ... c1m 0 1 c23 ... c2m ... 0 0 0 ... 1

В каком порядке ищутся элементы матриц B и C при факторизации А = B × C

Процесс нахождения матриц B и C размерами m × m разбивается на m этапов, причём на каждом этапе сначала по формуле b_ij = a_ij − Σ_l=1^j−1 b_il×c_lj находится элемент матрицы B, находящийся на диагонали, после чего находится строка матрицы C, после чего находятся остальные элементы столбца матрицы B.

Условие существования и единственности разложения А = B × C

Все главные угловые миноры A отличны от 0:

A1 = a11 ≠ 0

;

A2 = ( a11 a12 ) ≠ 0 a21 a22

;

…;

Ai = ( a11 ... a1i ) ≠ 0 ... ai1 ... aii

Связь метода Гаусса с разложением A = B × C

Три этапа метода Гаусса соответствуют трём этапам факторизации:

• В методе Гаусса для того, чтобы свести матрицу к верхнетреугольной матрице с единицами на главной диагонали, требуется ^(m3 − m)/₃ операций — то же количество действий требуется для нахождения матриц B и C
• Для решения уравнения By = f  требуется ^m(m + 1)/₂ действий — в точности то число действий, которое требуется для вычисления правой части в методе Гаусса
• Для решения уравнения Cx =  y  требуется ^m(m − 1)/₂ действий — в точности то число действий, которое требуется для обратного хода Гаусса

Метод Гаусса-Жордана

Метод Гаусса-Жордана:

• Обозначим A⁻¹ = X. Тогда AX = E
• Запишем в явном виде:
• ∑_{l = 1}^ma_ilx_lj = δ_ij, i, j = 1..m
• m² неизвестных, поэтому действий m⁶
• Разумно организовав алгоритм, можно получить порядка m³ действий

Метод квадратного корня (метод Холецкого)

• Решаем уравнение Ax = f
• |A| ≠ 0 (m × m)
• A = A* ⇔ a_ij = a_ji
• A = A^T — для вещественных матриц

Факторизуем матрицу A в виде A = S*DS

	s11	s12	s13	...	s1m
	0	s22	s23	...	s2m
S =	0	0	s33	..	s3m
	...
	0	0	0	...	smm

s_ii > 0, i = 2…m

D = diag (d₁₁, …, d_mm) d_ii = ±1, i = 1..m

Тогда система решается следующим образом:

• S*DSx = f
• S*Dy = f
• Sx = y

Эти две системы решаются явным образом, ибо матрицы треугольные.

Достоинства и недостатки метода квадратного корня

Плюс:

• Количество действий сокращается в два раза (^m3/₆ умножений и делений + m извлечений корня)

Минусы:

• Только для эрмитовых матриц

Что значит «решить СЛАУ итерационным методом»

• x_iⁿ — i-я кордината, n-я итерация
• x⁰ — начальное приближение

Далее организуется процесс так, что lim_{n → ∞}xⁿ → x, то есть, в некоторой норме |xⁿ − x| < ε, ε > 0

Вопросы, рассматриваемые при исследовании итерационного метода

• Будет ли сходиться. При каких параметрах и начальном приближении будет сходиться, при каких нет.
• С какой скоростью

Метод Якоби

• x_i^{n + 1} = ^f_i/_aii − ∑_{j = 1}^{i − 1 a_ij}/_aiix_jⁿ − ∑_{j = i + 1}^{m a_ij}/_aiix_jⁿ, n ∈ ℕ ∪ {0}
• x⁰ — задано

Достоинства и недостатки метода Якоби

Плюс:

• Данный метод реализуется достаточно просто

Минус:

• Очень медленная сходимость

Метод Зейделя

• x_i^{n + 1} = ^f_i/_aii − ∑_{j = 1}^{i − 1 a_ij}/_aiix_j^{n + 1} − ∑_{j = i + 1}^{m a_ij}/_aiix_jⁿ, n ∈ ℕ ∪ {0} (3)
• x⁰ — задано

Соотношение сложностей методов Якоби и Зейделя

По сложности и скорости сходимости эти два метода одинаковы.

Двуслойная запись

Двуслойная запись — когда связываются две соседние итерации.

Каноническая форма записи двуслойного итерационного метода решения СЛАУ

Определение. Канонической формой записи двуслойного итерационного метода решения системы Ax = f, A (m × m), det A ≠ 0 называется его запись в виде:

• B_{n + 1} ^{(xn + 1 − xn)}/_{τn + 1} + Axⁿ = f (4)

где

• τ_{n + 1} > 0, n ∈ ℕ ∪ {0}
• x⁰ — задано
• ∃B_{n + 1}⁻¹

Виды итерационных методов

• Метод явный, если B_{n + 1} = E. Если матрица диагональная, то тоже явный.
• Метод стационарный, если
  • B_{n + 1} = B
  • τ_{n + 1} = τ

Метод простой итерации

Метод простой итерации (МПИ):

• (МПИ) (xⁿ⁺¹ − xⁿ)/τ + Axⁿ = f, x⁰ — задано, n ∈ ℕ ∪ {0}, τ > 0
• Если τ меняется, то это другой метод, для которого оптимален Чебышевский набор параметров.

Попеременно-треугольный итерационный метод (метод Самарского) (ПТИМ)

• A = R₁ + R₂, где R₁ — нижнетреугольная матрица с диагональными элементам r_1ii = a_ii/2, R₂ — верхнетреугольная матрица с диагональными элементам r_2ii = a_ii/2.
• (E + ωR₁)(E + ωR₂)((x^{n + 1} − xⁿ)/τ) + Axⁿ = f (5)
  • n ∈ ℕ ∪ {0}, x⁰ задано, ω > 0, τ > 0
• Применительно к канонической записи B = (E + ωR₁)(E + ωR₂)

Невязка

rⁿ = f − Axⁿ

Энергетическая норма

Энергетическая норма ||x||_D = (Dx,x)^1/₂, где D — положительно определённый опрератор, то есть (Dx, x) > 0, ∀ x ≠ 0.

Вектор погрешности

Вектор погрешности: vⁿ = xⁿ − x.

Матрица перехода

S = E − τB⁻¹A

Вывод:

• Ax = f
• ∃ A⁻¹ (m × m)
• B ^{(xn + 1 − xn)}/_τ + Axⁿ = f
• xⁿ = vⁿ + x
• B (v^n + 1 − vⁿ)/τ + Avⁿ = 0
• (v^n + 1 − vⁿ)/τ + B⁻¹Avⁿ = 0
• vⁿ⁺¹ = vⁿ − τB⁻¹Avⁿ = (E − τB⁻¹A)vⁿ
• S = E − τB⁻¹A

Условие сходимости матрицы при любом начальном приближении, условие на матрицу перехода

Теорема 1. Итерационный метод B ^{(xn + 1 − xn)}/_τ + Axⁿ = f решения системы Ax = f сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы S = E − τB⁻¹A по модулю меньше 1: |λ_k^S| < 1.

Это означает, что оператор S — сжимающий.

Достаточное условие сходимости итерационного метода (теорема Самарского)

Теорема (Самарского, о достаточном условии сходимости метода B ^{(xn + 1 − xn)}/_τ + Axⁿ = f). Пусть есть A = A* = A^T > 0 (симметрический положительно определённый оператор (матрица)) и выполненно операторное (матричное) неравенство B − 0,5τA > 0, τ > 0. Тогда итерационный метод сходится при любом начальном приближении в среднеквадратичной норме ||xⁿ − x|| = (∑_{i = 1}^m (x_iⁿ − xi)²)^1/₂ → 0, n → ∞.

Теорема о сходимости метода Якоби

Следствие 1 теоремы Самарского. Пусть ∃ A = A* > 0, 2D > A. Тогда Методя Якоби сходится при любом начальном приближении.

Теорема о сходимости метода простой итерации

Следствие 3 теоремы Самарского. Пусть ∃ A = A* > 0, γ₂ = max_{1 ≤ x ≤ m}λ_k^A > 0. Тогда 0 < τ < 2/γ₂ МПИ сходится при ∀ x⁰

Теорема о сходимости метода Зейделя

Следствие 4. Пусть ∃ A = A* > 0, 2D > A. Тогда метод Зейделя сходится при любом начальном приближении в среднеквадратичной норме. Вообще достаточно только самосопряженности оператора А: A = A* > 0

Скорость сходимости итерационного метода

ln ¹/_ρ — скорость сходимости итерационного метода

Оценка скорости сходимости итерационного метода

Теорема (об оценке скорости сходимости итерационного метода). Пусть

• A = A* > 0
• B = B* > 0
• 0 < ρ < 1
• ^{1 − ρ}/_τB ≤ A ≤ ^{1 + ρ}/_τB

Тогда итерационный метод B ^{(xn + 1 − xn)}/_τ + Axⁿ = f сходится к решению СЛАУ Ax = f и имеет место оценка ||v^{n + 1}||_B ≤ ρ||vⁿ||

Равенство Парсеваля

Равенство Парсеваля Пусть D = D* > 0, ∃ ортонормированный базис из собственных векторов x = ∑_k = 1^mc_ke_k.

Тогда равенство Парсиваля есть ||x||² = ∑_k = 1^mc_k²

Оценка скорости сходимости МПИ

Следствие 2 из теоремы об оценке скорости сходимости итерационного метода. Пусть A = a* > 0,

• γ₁ = min_{1 ≤ k ≤ m} λ_k^A, > 0 в силу положительной определённости
• γ₂ = max_{1 ≤ k ≤ m} λ_k^A

Тогда МПИ (xⁿ⁺¹ − xⁿ)/τ + Axⁿ = f, где τ = ²/_{γ1 + γ2}, ρ = ^{1 − ξ}/_{1 + ξ}, ξ = ^γ₁/_γ2 — сходится, имеет место оценка ||xⁿ − x|| ≤ ρ||xⁿ − x||

Теорема о сходимости ПТИМ

Теорема (о сходимости ПТИМ). Пусть A = A* > 0, ω > ^τ/₄. Тогда ПТИМ сходится в среднеквадратичной норме при любом начальном приближении.

Теорема об оценке скорости сходимости ПТИМ

Теорема (об оценке скорости сходимости ПТИМ). Пусть A = A* > 0. Пусть существуют такие две константы δ > 0, Δ > 0:

• A ≥ δE, R₂*R₂ ≤ ^Δ/₄ A (2)
• Положим ω = ²/_√δΔ, τ = ²/_{γ1 + γ2}, γ₁ = ^√δ/₂ (^√δΔ/_√δ+√Δ); γ₂ = ^√δΔ/₄
• ||x^{n + 1} − x||_B ≤ ρ ||xⁿ − x||_B
• где B = (E + ωR₂*)(E + ωR₂), ρ = ^{1 − √η}/_{1 + 3√η}, η = ^δ/_Δ
  • R₂* = R₁

Оценка скорости сходимости для метода простой итерации

• ||x^{n + 1} − x|| ≤ ρ ||xⁿ − x||, ρ = ^{1 − ξ}/_{1 + ξ}, ξ = ^γ₁/_γ2, ξ = η = O(m⁻²)
• 1/ρ = ^{1 + η}/_{1 − η} ≈ (1 + η)² ≈ 1 + 2η
• ln ¹/_ρ ≈ η, n₀(ε) = O(m²)

Задача на собственные значения

Есть совершенно произвольная вещественная матрица A. Нужно найти λ такие, что Ax = λx, x ≠ 0 (1)

• λ — собственные значения
• x — собственные вектора

Два круга проблем:

• Частичная проблема собственных значений — нужно находить только отдельные собственные значения (максимальное, минимальное)
• Полная проблема собственных значений — нужно находить все собственные значения

Всего m значений (с учётом кратности): λ_k, k = 1..m

Вообще говоря, собственные значения комплексные.

Все методы итерационные. Один из самых простых методов — степенной метод.

Степенной метод нахождения собственных значений

Степенной метод — метод, который описывается уравнением 1:

• x_{n + 1} = Ax_n (1)
• n = 0, 1, ..., x₀ — начальное приближение
• x_n = A_nx₀

Условия для степенного метода

• Предположения относительно матрицы A:
  • Все собственные значения расположены в порядке неубывания модуля: |λ₁| ≤ |λ₂| ≤ |λ₃| ≤ ... ≤ |λ_m|
  • Условие А: Мы рассматриваем класс матриц, для которфых существет базис из собственных векторов: {e_k}₁^m — базис из собственных векторов A (Ae_k = λ_ke_k, k = 1..m)
  • Ограничение B: последнее собственное значение не является кратным: |(λ_{m − 1})/(λ_m) < 1
  • Ограничение C: ∀ x = c₁e₁ + ... + c_me_m, c_m ≠ 0

Метод обратных итераций

1. ∃ A⁻¹. тогда нулевых собственных значений нет Кроме того, у обратной матрицы СЗ обратны к СЗ исходной матрицы. Тогда:
   • Ax_{n + 1} = x_n, n = 0, 1, …, x₀ — начальное приближение (3) Этот метод неявный. Перепишем его как:
   • x_{n + 1} = A⁻¹x_n (4)
   • x_n = (A⁻¹)ⁿx_n

Условия:
A) ∃ {e_k}₁^m из СВ
B) |λ₁/λ₂| < 1
C) x₀ = c₁e₁+ … + c_me_m, c₁ ≠ 0

Тогда:

• x_n = c₁λ₁⁻ⁿe₁+ … + c_mλ_m⁻ⁿe_m
• x_n/e₁λ₁⁻ⁿ = e₁ + … + (c_m/c₁)(λ₁/λ_m)ⁿe_m

Метод обратных итераций со сдигом

• (A − αE)x_{n + 1} = x_n (5)
  • n = 0, 1, …, x₀ — начальное приближение, α ∈ R
• ∃ (A − αE)⁻¹
• x_{n + 1} = (A − αE)⁻¹x_n
• x_n = e_l
• 1/|λ_l − α| = max_{1 ≤ k ≤ m} 1/|λ_k − α|

Что такое верхняя почти треугольная форма

Верхняя почти треугольная форма — форма, у которой обе побочных диагонали от главной ненулевые, а дальше треугольник из нулей.

Преобразование элементарных отражений (преобразование Хаусхолдера)

Определение. Преобразование элементарных отражений (Преобразование Хаусхолдера). Элементарным отражением, соответствующим данному вектору v называется преобразование, задаваемое матрицей: H = E − 2 vv^T/||v||²

QR-алгоритм решения полной проблемы собственных значений

∀ A = Q × R, Q⁻¹ = Q^T, R — верхнетреугольная матрица. Любую матрицу можно представить в виде данного разложения.

Количество действий для работы QR-алгоритма

• полная — O(m³)
• ВПТФ — O(m²)
• А - трехдиагональная - O(m)

Теорема о сохранении ВПТФ

Пусть C = B × A, B — ВТФ, A — ВПТФ. Тогда C — ВПТФ.

Глава 2

Задача интерполяции

Суть задачи: есть отрезок x ∈ [a, b]. Мы разбиваем его несовпадающими узлами a ≤ x₀ < x₁ < x₂ < … < x_n ≤ b — {x_i}₀ⁿ — узлы интерполирование (n + 1 штук). Есть f(x_i) = f_i, i = 0…n. Если полином P_n(x) = a₀ + a₁x + … a_nxⁿ такой, что P_n(x_i) = f(x_i), i = 0…n (1), то данный полином называется интерполяционным для f (интерполирует f).

Интерполяционный полином

Если полином P_n(x) = a₀ + a₁x + … a_nxⁿ такой, что P_n(x_i) = f(x_i), i = 0…n (1), то данный полином называется интерполяционным для f (интерполирует f).

Существование и единственность интерполяционного полинома

При условиях, накладываемых в постановке задачи интерполяции (узлы интерполирования не совпадают) интерполяционный полином существует и единственный.

Интерполяционный полином в форме Лагранжа

L_n(x) = ∑_{k = 0}ⁿ(ω(x))/((x −x_k)ω'(x_k)) × f(x_k), где

• ω(x) = (x − x₀)(x − x₁)…(x − x_n) = ∏_{i = 0}ⁿ(x_i − x_j)
• ω(x) = [ ](x − x_k)
• ω'(x) = [ ] + [ ]'(x − x_k)
• ω'(x_k) = ∏_{k ≠ j}ⁿ(x_k − x_j)

Определение погрешности интерполяционного полинома

Погрешность интерполяционной формулы Лагранжа ψ_Ln(x) = f(x) − L_n(x). Во всех узлах она будет совпадать: ψ_Ln(x_i) = 0.

Замечание 1. Если f(x) — полином степени ≤ n, то полином Лагранжа даёт точное приближение, то есть погрешность тождественно равна 0.

Замечание 2. По большому числу узлов интерполяцию проводят крайне редко. Можно подобрать узлы так, что при увеличении количества узлов сходимости не будет.

Разделённая разность

Разделённой разностью первого порядка, построенной по узлам x_i, x_j называется отношение f(x_i, x_j) = (f(x_j) − f(x_i)/(x_j − x_i))

Разделённая разность k+1-го порядка: пусть есть f(x_j, x_{j + 1}, …, x_{j + k}), f(x_{j + 1}, x_{j + 2}, …, x_{j + k + 1}) — разности k-го порядка. Тогда f(x_j, x_{j + 1}, …, x_{j + k + 1}) = (f(x_{j + 1}, x_{j + 2}, …, x_{j + k + 1}) − f(x_j, x_{j + 1}, …, x_{j + k}))/(x_{j + k + 1} − x_j) — разделённая разность k + 1-го порядка.

Выражение разделённой разности через значения функции в точках

Разделённая разность k-го порядка, построенная по узлам x₀, … x_k может быть записана как f(x₀, x₁, …, x_k) = ∑_{i = 0}^k(f(x_i))/(ω_{0, k}'(x_i))

Выражение разделённой разности через значение функции в 0-м узле и разделённую разность k-го порядка

f(x_k) = f(x₀) + (x_k − x₀)f(x₀, x₁) + (x_k − x₀)(x_k − x₁)f(x₀, x₁, x₂) + … + (x_k − x₀)(x_k − x₁)…(x_k − x_{k − 1})f(x₀, x₁, …, x_k)

Интерполяционная функция в форме Ньютона

N_n(x) = f(x₀) + (x − x₀)f(x₀, x₁) + (x − x₀)(x − x₁)f(x₀, x₁, x₂) + … + (x − x₀)(x − x₁)…(x − x_{n − 1})f(x₀, x₁, …, x_n)

Погрешность инторполяционной формулы Ньютона

Погрешность та же самая, но записана внешне по-другому:

|ψ_Nn(x)| = |f(x) − N_n(x)| ≤ M_{n + 1}/(n + 1)! × |ω(x)|, M_{n + 1} = sup_{a ≤ x≤ b} |f(x)^{(n + 1)}|

== Когда лучше использовать Ньютона, а когда — Лагранжа

• Ньютон удобен при постепенном добавлении узлов, когда их количество не фиксировано
• Лагранж удобен, когда количество узлов фиксировано, но они могут находиться в разных местах

Интерполяционная формула Эрмита

Пусть у нас есть узлы x₀, … x_m — m + 1 узел. Информация в узлах такая: в узле может быть задано значение производных:

x0	x1	…	xm
f(x0)	f(x1)	…	f(xm)
f'(x0)	f'(x1)	…	f'(xm)
…
f(a0 − 1)(x0)	f(a1 − 1)(x1)	…	f(am − 1)(xm)

• a_i ∈ N ( натуральное), i = 0…m
• a_i — кратность i-го узла

Цель: построить H_n(x)

Замечание. H_n⁽ⁱ⁾ = f⁽ⁱ⁾(x_k), k = 0…m, i = 0…a_k − 1 (1)

При выполнении условия a₀ + a₁ + … + a_m = n + 1 мы можем построить полином Эрмита, причём единственный.

Общий вид полинома Эрмита

H_n(x) = ∑_{k = 0}^m ∑_{i = 0}^{a_k − 1} c_{k, i}(x)f⁽ⁱ⁾(x_k)

• c_{k, i}(x) — полином n-й степени
• x_i — различные

H₃(x)

H₃(x) = c₀(x)f(x₀) + c₁(x)f(x₁) + c₂(x)f(x₂) + b₁(x)f'(x₁)

• c₀(x) = ((x − x₁)²(x − x₂))/((x₀ − x₁)²(x₀ − x₂))
• c₂(x) = ((x − x₁)²(x − x₀))/((x₂ − x₁)²(x₂ − x₀))
• b₁(x) = ((x − x₀)(x − x₁)(x − x₂))/((x₁ − x₀)(x₁ − x₂))
• c₁(x) = (x − x₀)(x − x₂)/((x₁ − x₀)²(x₁ − x₂)²)) × [1 − ((x − x₁)(2x₁ − x₀ − x₂))/((x₁ − x₀)(x₁ − x₂))]

Погрешность полинома Эрмита

• ψ_H3(x) = f(x) − H₃(x) = f⁽⁴⁾(ξ)/4!
• M₄ = sup_{x0 ≤ x ≤ x2} |f⁽⁴⁾(x)|
• |f(x) − H₃(x)| ≤ M₄/4! × |ω(x)|

Формула Симпсона

Пусть требуется найти ∫_a^b f(x)dx, f(x_i) = f_i, f(x_i+0,5h) = f_{i + 1/2}

По формуле Симпсона:

• ∫_{xi − 1}^x_i f(x)dx ≈ h/6 × (f_{i − 1} + 4f_{i − 1/2} + f_i)

Оценка погрешности формулы Симпсона

• M₄ = sup_{a ≤ x ≤ b} |f⁽⁴⁾(x)|
• Ψ_h(f) ≤ (h/2)⁴ (M₄(b − a))/180 = O(h⁴)

L₂ для функций

Пусть задан отрезок [a, b]. Рассматривается множество функций таких, что ∫_a^b f²(x)dx < ∞, f ∈ L₂. В этом функциональном пространстве вводим векторное произведение: ∀ f, g ∈ L₂: (f, g) = ∫_a^b f(x)g(x)dx. Норма: ||f|| = (f, f)^1/2 = (∫_a^b f²(x)dx)^1/2. Эта норма не согласована с нормой в дискретном L₂.

Наилучшее среднеквадратичное приближение

• Требуется найти такой обобщённый многочлен φ(x) = ∑_{k = 0}ⁿ c__kφ_k(x), что
  • ||f − φ(x)|| = ∫_a^b (f(x) − φ(x))²dx = min_φ(x)||f − φ(x)||_L2²

Отклонение

∫_a^b (f(x) − ∑_{k = 0}ⁿ c_kφ_k(x))²dx = ∫_a^b f(x)²dx − 2∑_{k = 0}ⁿ c_k ∫_a^b f(x)φ₀(x)dx + ∑_{l = 0}ⁿ c_l ∑_{k = 0}ⁿ c_k ∫_a^b φ₀²(x)dx = ∫_a^b f(x)²dx − ∑_{k = 0}ⁿ c_k² ≥ 0

• ∑_{k = 0}ⁿ c_k² ≤ ||f||² — неравенство Бесселя
• ∑_{k = 0}ⁿ c_k² = ||f||² — равенство Парсеваля

Глава 3

Нелинейная система

{	f1(x1, x2, …, xm) = 0
	f2(x1, x2, …, xm) = 0
	…
	fm(x1, x2, …, xm) = 0

• f: R_m → R_m
• f_ = (f₁, …, f_m)^T
• x_ = (x₁, …, x_m)^T
• f_ (x_) = 0

Задачи связанные с решением нелинейных уравнений и систем

1. Локализация корня x_*, f(x_*) = 0, указать область, где он находится. Этим мы заниматься не будем
2. Строится итерационный процесс, и аккуратно выбирая начальное приближение x₀ из локализованной области, x_n → x_*, n → ∞

Метод бисекции решения нелинейного уравнения

Второй метод более регулярный и он называется метод бисекции.

• f(a) < 0
• f(b) > 0
• Берётся x₀ = (a + b)/2
• Если f(x₀) > 0, то x_* ∈ (a, x₀)

Каждый раз мы сужаем в два раза промежуток, где находится корень

Метод простой итерации (МПИ)

• f(x) = 0 (1)
• x_* ∈ U_a(x_*) (по определению)
• x = S(x) (2)
• x_{n + 1} = S(x_n) (3)
• x₀ ∈(x_*)

S(x) выбирается следующим образом: S(x) = x + r(x)f(x) (4). Единственное требование на r(x): sign(r(x)) ≠ 0 при x ∈ U_a(x_*).

Условие наличия корня в отрезке при использовании МПИ

Если известно, что ∃ S'(x), и sup_{x ∈ Ua(x*)} |S'(x)| = q < 1, то МПИ сходится, x₀ ∈ U_a(x_*)

Специальный вид МПИ

(x_{n + 1} − x_n)/τ + f(x_n) = 0, τ > 0, x₀ ∈ U_a(x_*), n = 0, 1, 2, …

Границы выбора τ для МПИ, записанного в специальном виде для сходимость со скоростью геометрической прогрессии

−1 < 1 − τf'(x) < 1 ⇒ 0 < τ < 2/M₁

Метод Эйткена

Предположим, что x_n − x_* = Aqⁿ (6). Запишем три итерации:

• x_{n − 1} − x_* = Aq^{n − 1} (7)
• x_n − x_* = Aqⁿ (8)
• x_{n + 1} − x_* = Aq^{n +1} (9)

Тогда:

• x_* = x_n − ((x_{n + 1} − x_n)²)/(x_{n + 1} − 2x_n + x_{n − 1})

Но так как (6) неточно, то это оказывается хоть и достаточно точным, но приближением.

Метод Ньютона (касательных)

• f(x) = 0
• x_* ∈ U_a(x_*) (по определению)
• xⁿ — n-я итерация
• x^{n + 1} = xⁿ − f(xⁿ)/f'(xⁿ), n = 0, 1, …, x⁰ — начальное приближение (2)
• От функции требуется гладкость до третьей производной

Метод Ньютона очень быстро сходится, но он может зацикливаться.

Модифицированный метод Ньютона

• x^{n + 1} = xⁿ − f(xⁿ)/f'(x⁰), n = 0, 1, …, x⁰ — начальная итерация
• Скорость сходимости колеблется, но производительность повышается (особенно в системах) и позволяет избежать зацикливания

Метод Ньютона для системы из 2 уравнений

{	f1(x1, x2) = 0	(3)
	f2(x1, x2) = 0

(x₁^*, x₂^*) — решение

J(x) = (	(δf1/δx1)(x1n, x2n)	(δf1/δx2)(x1n, x2n)	)
	(δf2/δx1)(x1n, x2n)	(δf2/δx2)(x1n, x2n)

• ∃ J⁻¹(xⁿ)
• x^{n + 1} = xⁿ − J⁻¹(xⁿ)f(xⁿ), n = 0, 1, …, x⁰ ∈ U_a(x^*)

Метод Ньютона: общий случай для m уравнений

{	f1(x1, x2, …, xm) = 0	(6)
	f2(x1, x2, …, xm) = 0
	…
	fm(x1, x2, …, xm) = 0

• (J(x))_ij = (δf_i/δx_j), i, j = 1…m
• x^{n + 1} = xⁿ − J⁻¹(xⁿ)f(xⁿ), n = 0, 1, …, x⁰ ∈ U_a(x^*) (6)
• x^{n + 1} = xⁿ − J(x⁰)f(xⁿ)

Метод секущей (хорд)

• x^{n + 1} = xⁿ − f(xⁿ)/f'(x⁰), n = 0, 1, …
• f'(xⁿ) = (f(x^{n + 1}) − f(xⁿ))/(x^{n + 1} − xⁿ)

Комбинированный метод

Подставим в метод Ньютона приближение производной:

• x^{n + 1} = xⁿ − (xⁿ − x^{n − 1})f(xⁿ)/(f(xⁿ) − f(x^{n − 1}))

Скорость сходимости метода Ньютона

• Z_n = xⁿ − x_* — погрешность
• ∃ M > 0: 0,5|S''(x~_n)| ≤ M
• |Z_n| ≤ (M|Z₀|)²ⁿ/M = 1/M × q²ⁿ

Скорость сходимости модифицированного метода Ньютона

• S'(x) = 1 − f'(x)/f'(x⁰)
• S'(x_*) = 1 − f'(x_*)/f'(x₀)

Чем ближе это значение к нулю, тем ближе скорость сходимости к методу Ньютона.