Редактирование: Численные Методы, Определения

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

Версия от 11:28, 10 июня 2010; 81.200.2.121 (Обсуждение)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

ПРЕДУПРЕЖДЕНИЕ: Вы редактируете устаревшую версию данной страницы. После сохранения страницы будут потеряны изменения, сделанные в последующих версиях.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 44 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.

= Глава 1 =
== Система линейных алгебраических уравнений (СЛАУ) ==
'''Система линейных алгебраических уравнений:'''
* Ax = f
* A (m &times; m), det A &ne; 0 — решение есть, оно единственное
* x = (x1, x2, ... xm)T
* f = (f1, f2, ... fm)T

== Группы методов решения СЛАУ ==
К курсе рассматриваются две группы методов:
# Прямые (точные) методы
# Итерационные (приближённые) методы

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

== Задача на собственные значения ==
'''Задача на собственные значения''' — задача о нахождении такого числа &lambda;, что Ax = &lambda; &times; x, x &ne; 0 — собственный вектор, &lambda;&nbsp;&mdash; собственное значение.

== Факторизация матрицы ==
'''Факторизация матрицы''' — представление матрицы А в виде произведения B &times; C, где
{|
 |B — нижнетреугольная матрица:
 {|style="text-align:center"
 |b11
 |0
 |0
 |...
 |0
 |-
 |b21
 |b22
 |0
 |...
 |0
 |-
 |colspan="5"|...
 |-
 |b1m
 |b2m
 |b3m
 |...
 |bmm
 |}
 |C — верхнетреугольная матрица с единицами на диаонали:
 {|style="text-align:center"
 |1 
 |c12
 |c13
 |... 
 |c1m
 |-
 |0
 |1
 |c23
 |...
 |c2m
 |-
 |colspan="5"|...
 |-
 |0
 |0
 |0
 |...
 |1
 |}
 |}

== В каком порядке ищутся элементы матриц B и C при факторизации А = B &times; C ==
Процесс нахождения матриц B и C размерами m &times; m разбивается на m этапов, причём на каждом этапе сначала по формуле bij = aij &minus; &Sigma;l=1j&minus;1 bil&times;clj находится элемент матрицы B, находящийся на диагонали, после чего находится строка матрицы C, после чего находятся остальные элементы столбца матрицы B.

== Условие существования и единственности разложения А = B &times; C ==
Все главные угловые миноры A отличны от 0:
{|
 |A1 = a11 &ne; 0
 |;
 |
 {|style="text-align:center"
 |rowspan="2"|A2&nbsp;=&nbsp;(
 |a11
 |a12
 |rowspan="2"|)&nbsp;&ne;&nbsp;0
 |-
 |a21
 |a22
 |}
 |;
 |&hellip;;
 |
 {|style="text-align:center"
 |rowspan="3"|Ai&nbsp;=&nbsp;(
 |a11
 |...
 |a1i
 |rowspan="3"|)&nbsp;&ne;&nbsp;0
 |-
 |colspan="3"|...
 |-
 |ai1
 |...
 |aii
 |}
 |}

== Связь метода Гаусса с разложением A = B &times; C ==
Три этапа метода Гаусса соответствуют трём этапам факторизации:
* В методе Гаусса для того, чтобы свести матрицу к верхнетреугольной матрице с единицами на главной диагонали, требуется (m3&nbsp;&minus;&nbsp;m)/3 операций — то же количество действий требуется для нахождения матриц B и C
* Для решения уравнения By&nbsp;=&nbsp;f&nbsp; требуется m(m&nbsp;+&nbsp;1)/2 действий — в точности то число действий, которое требуется для вычисления правой части в методе Гаусса
* Для решения уравнения Cx&nbsp;= &nbsp;y&nbsp; требуется m(m&nbsp;&minus;&nbsp;1)/2 действий — в точности то число действий, которое требуется для обратного хода Гаусса

== Метод Гаусса-Жордана ==
'''Метод Гаусса-Жордана''':
* Обозначим A&minus;1 = X. Тогда AX = E
* Запишем в явном виде:
* &sum;l = 1mailxlj = &delta;ij, i, j = 1..m 
* m2 неизвестных, поэтому действий m6
* Разумно организовав алгоритм, можно получить порядка m3 действий

== Метод квадратного корня (метод Холецкого) ==
* Решаем уравнение Ax = f
* |A| &ne; 0 (m &times; m)
* A = A* &hArr; aij = aji
* A = AT &mdash; для вещественных матриц

Факторизуем матрицу A в виде A = S*DS
{|style="text-align:center"
 |
 |s11
 |s12
 |s13
 |...
 |s1m
 |-
 |
 |0
 |s22
 |s23
 |...
 |s2m
 |-
 |S = 
 |0
 |0
 |s33
 |..
 |s3m
 |-
 |
 |colspan="5"|...
 |-
 |
 |0
 |0
 |0
 |...
 |smm
 |}
sii > 0, i = 2&hellip;m

D = diag (d11, &hellip;, dmm) dii = &plusmn;1, i = 1..m

Тогда система решается следующим образом:
* S*DSx = f
* S*Dy = f
* Sx = y
Эти две системы решаются явным образом, ибо матрицы треугольные.

== Достоинства и недостатки метода квадратного корня ==
Плюс:
* Количество действий сокращается в два раза (m3/6 умножений и делений + m извлечений корня)
Минусы:
* Только для эрмитовых матриц

== Что значит «решить СЛАУ итерационным методом» ==
* xin — i-я кордината, n-я итерация
* x0 — начальное приближение

Далее организуется процесс так, что limn &rarr; &infin;xn &rarr; x, то есть, в некоторой норме |xn &minus; x| &lt; &epsilon;, &epsilon; &gt; 0

== Вопросы, рассматриваемые при исследовании итерационного метода ==
* Будет ли сходиться. При каких параметрах и начальном приближении будет сходиться, при каких нет.
* С какой скоростью

== Метод Якоби ==
* xin + 1 = fi/aii &minus; &sum;j = 1i &minus; 1 aij/aiixjn &minus; &sum;j = i + 1m aij/aiixjn, n &isin; ℕ &cup; {0}
* x0 — задано

== Достоинства и недостатки метода Якоби ==
Плюс:
* Данный метод реализуется достаточно просто
Минус:
* Очень медленная сходимость

== Метод Зейделя ==
* xin + 1 = fi/aii &minus; &sum;j = 1i &minus; 1 aij/aiixjn + 1 &minus; &sum;j = i + 1m aij/aiixjn, n &isin; ℕ &cup; {0} (3)
* x0 — задано

== Соотношение сложностей методов Якоби и Зейделя ==
По сложности и скорости сходимости эти два метода одинаковы.

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

== Каноническая форма записи двуслойного итерационного метода решения СЛАУ ==
'''Определение'''. Канонической формой записи двуслойного итерационного метода решения системы Ax = f, A (m &times; m), det A &ne; 0 называется его запись в виде:
* Bn + 1 (xn + 1 &minus; xn)/&tau;n + 1 + Axn = f (4)
где
* &tau;n + 1 > 0, n &isin; ℕ &cup; {0}
* x0 — задано
* &exist;Bn + 1&minus;1

== Виды итерационных методов ==
* Метод явный, если Bn + 1 = E. Если матрица диагональная, то тоже явный.
* Метод стационарный, если
** Bn + 1 = B
** &tau;n + 1 = &tau;

== Метод простой итерации ==
'''Метод простой итерации (МПИ)''':
* (МПИ) (xn+1 &minus; xn)/&tau; + Axn = f, x0 &mdash; задано, n &isin; ℕ &cup; {0}, &tau; > 0
* Если &tau; меняется, то это другой метод, для которого оптимален Чебышевский набор параметров.

== Попеременно-треугольный итерационный метод (метод Самарского) (ПТИМ) ==
* A = R1 + R2, где R1 — нижнетреугольная матрица с диагональными элементам r1ii = aii/2, R2 — верхнетреугольная матрица с диагональными элементам r2ii = aii/2.
* (E + &omega;R1)(E + &omega;R2)((xn + 1 &minus; xn)/&tau;) + Axn = f (5)
** n &isin; ℕ &cup; {0}, x0 задано, &omega; > 0, &tau; > 0
* Применительно к канонической записи B = (E + &omega;R1)(E + &omega;R2)

== Невязка ==
rn = f &minus; Axn

== Энергетическая норма ==
'''Энергетическая норма''' ||x||D&nbsp;=&nbsp;(Dx,x)1/2, где D — положительно определённый опрератор, то есть (Dx,&nbsp;x)&nbsp;>&nbsp;0, &forall;&nbsp;x&nbsp;&ne;&nbsp;0.

== Вектор погрешности ==
'''Вектор погрешности''': vn&nbsp;=&nbsp;xn&nbsp;&minus;&nbsp;x.

== Матрица перехода ==
'''S = E &minus; &tau;B&minus;1A'''

Вывод:
* Ax = f
* &exist; A&minus;1 (m &times; m)
* B (xn + 1 &minus; xn)/&tau; + Axn = f
* xn&nbsp;=&nbsp;vn&nbsp;+&nbsp;x
* B (vn&nbsp;+&nbsp;1 &minus; vn)/&tau; + Avn = 0
* (vn&nbsp;+&nbsp;1 &minus; vn)/&tau; + B&minus;1Avn = 0
* vn+1 = vn &minus; &tau;B&minus;1Avn = (E &minus; &tau;B&minus;1A)vn
* S = E &minus; &tau;B&minus;1A

== Условие сходимости матрицы при любом начальном приближении, условие на матрицу перехода ==
'''Теорема 1'''. Итерационный метод B (xn + 1 &minus; xn)/&tau; + Axn = f решения системы Ax = f сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы S = E &minus; &tau;B&minus;1A по модулю меньше 1: |&lambda;kS|&nbsp;<&nbsp;1.

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

== Достаточное условие сходимости итерационного метода (теорема Самарского) ==
'''Теорема (Самарского, о достаточном условии сходимости метода B (xn + 1 &minus; xn)/&tau; + Axn = f)'''. Пусть есть A&nbsp;=&nbsp;A*&nbsp;=&nbsp;AT&nbsp;>&nbsp;0 (симметрический положительно определённый оператор (матрица)) и выполненно операторное (матричное) неравенство B &minus; 0,5&tau;A&nbsp;>&nbsp;0, &tau;&nbsp;>&nbsp;0. Тогда итерационный метод сходится при любом начальном приближении в среднеквадратичной норме ||xn&nbsp;&minus;&nbsp;x||&nbsp;=&nbsp;(&sum;i = 1m (xin&nbsp;&minus;&nbsp;xi)2)1/2&nbsp;&rarr;&nbsp;0, n&nbsp;&rarr;&nbsp;&infin;.

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

== Теорема о сходимости метода простой итерации ==
'''Следствие 3 теоремы Самарского'''. Пусть &exist; A&nbsp;=&nbsp;A*&nbsp;>&nbsp;0, &gamma;2 = max1 &le; x &le; m&lambda;kA > 0. Тогда 0 < &tau; < 2/&gamma;2 МПИ сходится при &forall;&nbsp;x0

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

== Скорость сходимости итерационного метода ==
ln 1/&rho; — '''скорость сходимости итерационного метода'''

== Оценка скорости сходимости итерационного метода ==
'''Теорема (об оценке скорости сходимости итерационного метода)'''. Пусть 
* A = A* > 0
* B = B* > 0
* 0 &lt; &rho; &lt; 1
* 1 &minus; &rho;/&tau;B &le; A &le; 1 + &rho;/&tau;B
Тогда итерационный метод B (xn + 1 &minus; xn)/&tau; + Axn = f сходится к решению СЛАУ Ax = f и имеет место оценка ||vn + 1||B &le; &rho;||vn||

== Равенство Парсеваля ==
'''Равенство Парсеваля'''
Пусть D&nbsp;=&nbsp;D*&nbsp;>&nbsp;0, &exist; ортонормированный базис из собственных векторов x&nbsp;=&nbsp;&sum;k&nbsp;=&nbsp;1mckek.

Тогда равенство Парсиваля есть ||x||2&nbsp;=&nbsp;&sum;k&nbsp;=&nbsp;1mck2

== Оценка скорости сходимости МПИ ==
'''Следствие 2 из теоремы об оценке скорости сходимости итерационного метода.''' Пусть A = A* > 0,
* &gamma;1 = min1 &le; k &le; m &lambda;kA, > 0 в силу положительной определённости
* &gamma;2 = max1 &le; k &le; m &lambda;kA

Тогда МПИ (xn+1 &minus; xn)/&tau; + Axn = f, где &tau; = 2/&gamma;1 + &gamma;2, &rho; = 1 &minus; &xi;/1 + &xi;, &xi; = &gamma;1/&gamma;2 — сходится, имеет место оценка ||xn+1 &minus; x|| &le; &rho;||xn &minus; x||

== Теорема о сходимости ПТИМ ==
'''Теорема (о сходимости ПТИМ)'''. Пусть A = A* > 0, &omega; > &tau;/4. Тогда ПТИМ сходится в среднеквадратичной норме при любом начальном приближении.

== Теорема об оценке скорости сходимости ПТИМ ==
'''Теорема (об оценке скорости сходимости ПТИМ)'''. Пусть A = A* > 0. Пусть существуют такие две константы &delta; > 0, &Delta; > 0: 
* A &ge; &delta;E, R2*R2 &le; &Delta;/4 A (2)
* Положим &omega; = 2/√&delta;&Delta;, &tau; = 2/&gamma;1 + &gamma;2, &gamma;1 = √&delta;/2 (√&delta;&Delta;/√&delta;+√&Delta;); &gamma;2 = √&delta;&Delta;/4
* ||xn + 1 &minus; x||B &le; &rho; ||xn &minus; x||B
* где B = (E + &omega;R2*)(E + &omega;R2), &rho; = 1 &minus; √&eta;/1 + 3√&eta;, &eta; = &delta;/&Delta;
** R2* = R1

== Оценка скорости сходимости для метода простой итерации ==
* ||xn + 1 &minus; x|| &le; &rho; ||xn &minus; x||, &rho; = 1 &minus; &xi;/1 + &xi;, &xi; = &gamma;1/&gamma;2, &xi; = &eta; = O(m&minus;2)
* 1/&rho; = 1 + &eta;/1 &minus; &eta; &asymp; (1 + &eta;)2 &asymp; 1 + 2&eta;
* ln 1/&rho; &asymp; &eta;, n0(&epsilon;) = O(m2)

== Задача на собственные значения ==
Есть совершенно произвольная вещественная матрица A. Нужно найти &lambda; такие, что Ax = &lambda;x, x &ne; 0 (1)
* &lambda; — собственные значения
* x — собственные вектора

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

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

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

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

== Степенной метод нахождения собственных значений ==
'''Степенной метод''' — метод, который описывается уравнением 1:
* xn + 1 = Axn (1)
* n = 0, 1, ..., x0 — начальное приближение
* xn = Anx0

== Условия для степенного метода ==
* Предположения относительно матрицы A:
** Все собственные значения расположены в порядке неубывания модуля: |&lambda;1| &le; |&lambda;2| &le; |&lambda;3| &le; ... &le; |&lambda;m|
** Условие А: Мы рассматриваем класс матриц, для которфых существет базис из собственных векторов: {ek}1m — базис из собственных векторов A (Aek = &lambda;kek, k = 1..m)
** Ограничение B: последнее собственное значение не является кратным: |(&lambda;m &minus; 1)/(&lambda;m) < 1
** Ограничение C: &forall; x = c1e1 + ... + cmem, cm &ne; 0

== Метод обратных итераций ==
# &exist; A&minus;1. тогда нулевых собственных значений нет Кроме того, у обратной матрицы СЗ обратны к СЗ исходной матрицы. Тогда:
#* Axn + 1 = xn, n = 0, 1, &hellip;, x0 — начальное приближение (3) Этот метод неявный. Перепишем его как:
#* xn + 1 = A&minus;1xn (4)
#* xn = (A&minus;1)nxn

Условия: 
A) &exist; {ek}1m из СВ 
B) |&lambda;1/&lambda;2| < 1 
C) x0 = c1e1+ &hellip; + cmem, c1 &ne; 0

Тогда:
* xn = c1&lambda;1&minus;ne1+ &hellip; + cm&lambda;m&minus;nem
* xn/e1&lambda;1&minus;n = e1 + &hellip; + (cm/c1)(&lambda;1/&lambda;m)nem

== Метод обратных итераций со сдигом ==
* (A &minus; &alpha;E)xn + 1 = xn (5)
** n = 0, 1, &hellip;, x0 — начальное приближение, &alpha; &isin; R
* &exist; (A &minus; &alpha;E)&minus;1
* xn + 1 = (A &minus; &alpha;E)&minus;1xn
* xn = el
* 1/|&lambda;l &minus; &alpha;| = max1 &le; k &le; m 1/|&lambda;k &minus; &alpha;|

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

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

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

&forall; A = Q &times; R, Q&minus;1 = QT, R — верхнетреугольная матрица. Любую матрицу можно представить в виде данного разложения.

== Количество действий для работы QR-алгоритма ==
* полная — O(m3)
* ВПТФ — O(m2)
* А - трехдиагональная - O(m)

== Теорема о сохранении ВПТФ ==
Пусть C = B &times; A, B — ВТФ, A — ВПТФ. Тогда C — ВПТФ.

= Глава 2 =
== Задача интерполяции ==
Суть задачи: есть отрезок x &isin; [a, b]. Мы разбиваем его несовпадающими узлами a &le; x0 &lt; x1 &lt; x2 &lt; &hellip; &lt; xn &le; b — {xi}0n — узлы интерполирование (n + 1 штук). Есть f(xi) = fi, i = 0&hellip;n. Если полином Pn(x) = a0 + a1x + &hellip; anxn такой, что Pn(xi) = f(xi), i = 0&hellip;n (1), то данный полином называется интерполяционным для f (интерполирует f).

== Интерполяционный полином ==
Если полином Pn(x) = a0 + a1x + &hellip; anxn такой, что Pn(xi) = f(xi), i = 0&hellip;n (1), то данный полином называется '''интерполяционным''' для f (интерполирует f).

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

== Интерполяционный полином в форме Лагранжа ==
Ln(x) = &sum;k = 0n(&omega;(x))/((x &minus;xk)&omega;'(xk)) &times; f(xk), где 
* &omega;(x) = (x &minus; x0)(x &minus; x1)&hellip;(x &minus; xn) = &prod;i = 0n(xi &minus; xj)
* &omega;(x) = [ ](x &minus; xk)
* &omega;'(x) = [ ] + [ ]'(x &minus; xk)
* &omega;'(xk) = &prod;k &ne; jn(xk &minus; xj)

== Определение погрешности интерполяционного полинома ==
Погрешность интерполяционной формулы Лагранжа &psi;Ln(x) = f(x) &minus; Ln(x). Во всех узлах она будет совпадать: &psi;Ln(xi) = 0.

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

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

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

'''Разделённой разностью первого порядка''', построенной по узлам xi, xj называется отношение f(xi, xj) = (f(xj) &minus; f(xi)/(xj &minus; xi))

'''Разделённая разность k+1-го порядка''': пусть есть f(xj, xj + 1, &hellip;, xj + k), f(xj + 1, xj + 2, &hellip;, xj + k + 1) — разности k-го порядка. Тогда f(xj, xj + 1, &hellip;, xj + k + 1) = (f(xj + 1, xj + 2, &hellip;, xj + k + 1) &minus; f(xj, xj + 1, &hellip;, xj + k))/(xj + k + 1 &minus; xj) — разделённая разность k + 1-го порядка.

== Выражение разделённой разности через значения функции в точках ==
Разделённая разность k-го порядка, построенная по узлам x0, &hellip; xk может быть записана как f(x0, x1, &hellip;, xk) = &sum;i = 0k(f(xi))/(&omega;0, k'(xi))

== Выражение разделённой разности через значение функции в 0-м узле и разделённую разность k-го порядка == 
f(xk) = f(x0) + (xk &minus; x0)f(x0, x1) + (xk &minus; x0)(xk &minus; x1)f(x0, x1, x2) + &hellip; + (xk &minus; x0)(xk &minus; x1)&hellip;(xk &minus; xk &minus; 1)f(x0, x1, &hellip;, xk)

== Интерполяционная функция в форме Ньютона ==
Nn(x) = f(x0) + (x &minus; x0)f(x0, x1) + (x &minus; x0)(x &minus; x1)f(x0, x1, x2) + &hellip; + (x &minus; x0)(x &minus; x1)&hellip;(x &minus; xn &minus; 1)f(x0, x1, &hellip;, xn)

== Погрешность инторполяционной формулы Ньютона ==
Погрешность та же самая, но записана внешне по-другому:

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

== Интерполяционная формула Эрмита ==
Пусть у нас есть узлы x0, &hellip; xm — m + 1 узел. Информация в узлах такая: в узле может быть задано значение производных:
{|
 |x0
 |x1
 |&hellip;
 |xm
 |-
 |f(x0)
 |f(x1)
 |&hellip;
 |f(xm)
 |-
 |f'(x0)
 |f'(x1)
 |&hellip;
 |f'(xm)
 |-
 |&hellip;
 |-
 |f(a0 &minus; 1)(x0)
 |f(a1 &minus; 1)(x1)
 |&hellip;
 |f(am &minus; 1)(xm)
 |}

* ai &isin; N ( натуральное), i = 0&hellip;m
* ai — кратность i-го узла

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

Замечание. Hn(i) = f(i)(xk), k = 0&hellip;m, i = 0&hellip;ak &minus; 1 (1)

При выполнении условия a0 + a1 + &hellip; + am = n + 1 мы можем построить полином Эрмита, причём единственный.

== Общий вид полинома Эрмита ==
Hn(x) = &sum;k = 0m &sum;i = 0ak &minus; 1 ck, i(x)f(i)(xk)
* ck, i(x) — полином n-й степени
* xi — различные

== H3(x) ==
H3(x) = c0(x)f(x0) + c1(x)f(x1) + c2(x)f(x2) + b1(x)f'(x1)
* c0(x) = ((x &minus; x1)2(x &minus; x2))/((x0 &minus; x1)2(x0 &minus; x2))
* c2(x) = ((x &minus; x1)2(x &minus; x0))/((x2 &minus; x1)2(x2 &minus; x0))
* b1(x) = ((x &minus; x0)(x &minus; x1)(x &minus; x2))/((x1 &minus; x0)(x1 &minus; x2))
* c1(x) = (x &minus; x0)(x &minus; x2)/((x1 &minus; x0)2(x1 &minus; x2)2)) &times; [1 &minus; ((x &minus; x1)(2x1 &minus; x0 &minus; x2))/((x1 &minus; x0)(x1 &minus; x2))]

== Формула Симпсона ==
Пусть требуется найти ∫ab f(x)dx, f(xi) = fi, f(xi+0,5h) = fi + 1/2

По формуле Симпсона:
* ∫xi &minus; 1xi f(x)dx &asymp; h/6 &times; (fi &minus; 1 + 4fi &minus; 1/2 + fi)

== Оценка погрешности формулы Симпсона ==
* M4 = supa &le; x &le; b |f(4)(x)|
* &Psi;h(f) &le; (h/2)4 (M4(b &minus; a))/180 = O(h4)

== L2 для функций ==
Пусть задан отрезок [a, b]. Рассматривается множество функций таких, что ∫ab f2(x)dx &lt; &infin;, f &isin; L2. В этом функциональном пространстве вводим векторное произведение: &forall; f, g &isin; L2: (f, g) = &int;ab f(x)g(x)dx. Норма: ||f|| = (f, f)1/2 = (&int;ab f2(x)dx)1/2. Эта норма не согласована с нормой в дискретном L2.

== Наилучшее среднеквадратичное приближение ==
* Требуется найти такой обобщённый многочлен &phi;(x) = &sum;k = 0n c_k&phi;k(x), что
** ||f &minus; &phi;(x)|| = &int;ab (f(x) &minus; &phi;(x))2dx = min&phi;(x)||f &minus; &phi;(x)||L22

== Отклонение ==
&int;ab (f(x) &minus; &sum;k = 0n ck&phi;k(x))2dx = &int;ab f(x)2dx &minus; 2&sum;k = 0n ck &int;ab f(x)&phi;0(x)dx + &sum;l = 0n cl &sum;k = 0n ck &int;ab &phi;02(x)dx = &int;ab f(x)2dx &minus; &sum;k = 0n ck2 &ge; 0
* &sum;k = 0n ck2 &le; ||f||2 — неравенство Бесселя
* &sum;k = 0n ck2 = ||f||2 — равенство Парсеваля

= Глава 3 =
== Нелинейная система ==
{|
 |rowspan = "4"|{
 |f1(x1, x2, &hellip;, xm) = 0
 |-
 |f2(x1, x2, &hellip;, xm) = 0
 |-
 |&hellip;
 |-
 |fm(x1, x2, &hellip;, xm) = 0
 |}

* f: Rm &rarr; Rm
* f_ = (f1, &hellip;, fm)T
* x_ = (x1, &hellip;, xm)T
* f_ (x_) = 0

== Задачи связанные с решением нелинейных уравнений и систем ==
# Локализация корня x*, f(x*) = 0, указать область, где он находится. Этим мы заниматься не будем
# Строится итерационный процесс, и аккуратно выбирая начальное приближение x0 из локализованной области, xn &rarr; x*, n &rarr; &infin;

== Метод бисекции решения нелинейного уравнения ==
Второй метод более регулярный и он называется метод бисекции.
* f(a) < 0
* f(b) > 0
* Берётся x0 = (a + b)/2
* Если f(x0) > 0, то x* &isin; (a, x0)
Каждый раз мы сужаем в два раза промежуток, где находится корень

== Метод простой итерации (МПИ) ==
* f(x) = 0 (1)
* x* &isin; Ua(x*) (по определению)
* x = S(x) (2)
* xn + 1 = S(xn) (3)
* x0 &isin;(x*)

S(x) выбирается следующим образом: S(x) = x + r(x)f(x) (4). Единственное требование на r(x): sign(r(x)) &ne; 0 при x &isin; Ua(x*).

== Условие наличия корня в отрезке при использовании МПИ ==
Если известно, что &exist; S'(x), и supx &isin; Ua(x*) |S'(x)| = q &lt; 1, то МПИ сходится, x0 &isin; Ua(x*)

== Специальный вид МПИ ==
(xn + 1 &minus; xn)/&tau; + f(xn) = 0, &tau; &gt; 0, x0 &isin; Ua(x*), n = 0, 1, 2, &hellip;

== Границы выбора &tau; для МПИ, записанного в специальном виде для сходимость со скоростью геометрической прогрессии ==
&minus;1 &lt; 1 &minus; &tau;f'(x) &lt; 1 &rArr; 0 &lt; &tau; &lt; 2/M1

== Метод Эйткена ==
Предположим, что xn &minus; x* = Aqn (6). Запишем три итерации:
* xn &minus; 1 &minus; x* = Aqn &minus; 1 (7)
* xn &minus; x* = Aqn (8)
* xn + 1 &minus; x* = Aqn +1 (9)
Тогда:
* x* = xn &minus; ((xn + 1 &minus; xn)2)/(xn + 1 &minus; 2xn + xn &minus; 1)
Но так как (6) неточно, то это оказывается хоть и достаточно точным, но приближением.

== Метод Ньютона (касательных) ==
* f(x) = 0
* x* &isin; Ua(x*) (по определению)
* xn — n-я итерация
* xn + 1 = xn &minus; f(xn)/f'(xn), n = 0, 1, &hellip;, x0 — начальное приближение (2)
* От функции требуется гладкость до третьей производной
Метод Ньютона очень быстро сходится, но он может зацикливаться.

== Модифицированный метод Ньютона ==
* xn + 1 = xn &minus; f(xn)/f'(x0), n = 0, 1, &hellip;, x0 — начальная итерация
* Скорость сходимости колеблется, но производительность повышается (особенно в системах) и позволяет избежать зацикливания

== Метод Ньютона для системы из 2 уравнений ==
{|
 |rowspan= "2"|{
 |f1(x1, x2) = 0
 |rowspan="2"| (3)
 |-
 |f2(x1, x2) = 0
 |}

(x1*, x2*) — решение

{|
 |rowspan= "2"|J(x) = (
 |(&delta;f1/&delta;x1)(x1n, x2n) 
 |(&delta;f1/&delta;x2)(x1n, x2n) 
 |rowspan= "2"|)
 |-
 |(&delta;f2/&delta;x1)(x1n, x2n) 
 |(&delta;f2/&delta;x2)(x1n, x2n) 
 |}

* &exist; J&minus;1(xn)
* xn + 1 = xn &minus; J&minus;1(xn)f(xn), n = 0, 1, &hellip;, x0 &isin; Ua(x*)

== Метод Ньютона: общий случай для m уравнений ==
{|
 |rowspan= "4"|{
 |f1(x1, x2, &hellip;, xm) = 0
 |rowspan="4"| (6)
 |-
 |f2(x1, x2, &hellip;, xm) = 0
 |-
 |&hellip;
 |-
 |fm(x1, x2, &hellip;, xm) = 0
 |-
 |}

* (J(x))ij = (&delta;fi/&delta;xj), i, j = 1&hellip;m
* xn + 1 = xn &minus; J&minus;1(xn)f(xn), n = 0, 1, &hellip;, x0 &isin; Ua(x*) (6)
* xn + 1 = xn &minus; J(x0)f(xn)

== Метод секущей (хорд) ==
* xn + 1 = xn &minus; f(xn)/f'(x0), n = 0, 1, &hellip;
* f'(xn) = (f(xn + 1) &minus; f(xn))/(xn + 1 &minus; xn)

== Комбинированный метод ==
Подставим в метод Ньютона приближение производной:
* xn + 1 = xn &minus; (xn &minus; xn &minus; 1)f(xn)/(f(xn) &minus; f(xn &minus; 1))

== Скорость сходимости метода Ньютона ==
* Zn = xn &minus; x* — погрешность
* &exist; M &gt; 0: 0,5|S'&#39;(x~n)| &le; M
* |Zn| &le; (M|Z0|)2n/M = 1/M &times; q2n

== Скорость сходимости модифицированного метода Ньютона ==
* S'(x) = 1 &minus; f'(x)/f'(x0)
* S'(x*) = 1 &minus; f'(x*)/f'(x0)
Чем ближе это значение к нулю, тем ближе скорость сходимости к методу Ньютона.

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице: