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

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

Перейти к: навигация, поиск

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

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

Текущая версия Ваш текст
Строка 1: Строка 1:
-
= Глава 1 =
+
== From Ebaums Inc to MurkLoar. ==
-
== Система линейных алгебраических уравнений (СЛАУ) ==
+
We at EbaumsWorld consider you as disgrace of human race.
-
'''Система линейных алгебраических уравнений:'''
+
Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated.
-
* Ax = f
+
Dig yourself a grave - you will need it.
-
* A (m × m), det A ≠ 0 — решение есть, оно единственное
+
-
* x = (x<sub>1</sub>, x<sub>2</sub>, ... x<sub>m</sub>)<sup>T</sup>
+
-
* f = (f<sub>1</sub>, f<sub>2</sub>, ... f<sub>m</sub>)<sup>T</sup>
+
-
 
+
-
== Группы методов решения СЛАУ ==
+
-
К курсе рассматриваются две группы методов:
+
-
# Прямые (точные) методы
+
-
# Итерационные (приближённые) методы
+
-
 
+
-
== Прямой метод решения СЛАУ ==
+
-
'''Прямой метод решения СЛАУ'''&nbsp;&mdash; метод, который позволяет реализовать в алгоритме определённые формулы, то есть аналитическое решение.
+
-
 
+
-
== Задача на собственные значения ==
+
-
'''Задача на собственные значения''' — задача о нахождении такого числа &lambda;, что Ax = &lambda; &times; x, x &ne; 0 — собственный вектор, &lambda;&nbsp;&mdash; собственное значение.
+
-
 
+
-
== Факторизация матрицы ==
+
-
'''Факторизация матрицы''' — представление матрицы А в виде произведения B &times; C, где
+
-
{|
+
-
|B — нижнетреугольная матрица:
+
-
{|style="text-align:center"
+
-
|b<sub>11</sub>
+
-
|0
+
-
|0
+
-
|...
+
-
|0
+
-
|-
+
-
|b<sub>21</sub>
+
-
|b<sub>22</sub>
+
-
|0
+
-
|...
+
-
|0
+
-
|-
+
-
|colspan="5"|...
+
-
|-
+
-
|b<sub>1m</sub>
+
-
|b<sub>2m</sub>
+
-
|b<sub>3m</sub>
+
-
|...
+
-
|b<sub>mm</sub>
+
-
|}
+
-
|C — верхнетреугольная матрица с единицами на диаонали:
+
-
{|style="text-align:center"
+
-
|1
+
-
|c<sub>12</sub>
+
-
|c<sub>13</sub>
+
-
|...
+
-
|c<sub>1m</sub>
+
-
|-
+
-
|0
+
-
|1
+
-
|c<sub>23</sub>
+
-
|...
+
-
|c<sub>2m</sub>
+
-
|-
+
-
|colspan="5"|...
+
-
|-
+
-
|0
+
-
|0
+
-
|0
+
-
|...
+
-
|1
+
-
|}
+
-
|}
+
-
 
+
-
== В каком порядке ищутся элементы матриц B и C при факторизации А = B &times; C ==
+
-
Процесс нахождения матриц B и C размерами m &times; m разбивается на m этапов, причём на каждом этапе сначала по формуле b<sub>ij</sub> = a<sub>ij</sub> &minus; &Sigma;<sub>l=1</sub><sup>j&minus;1</sup> b<sub>il</sub>&times;c<sub>lj</sub> находится элемент матрицы B, находящийся на диагонали, после чего находится строка матрицы C, после чего находятся остальные элементы столбца матрицы B.
+
-
 
+
-
== Условие существования и единственности разложения А = B &times; C ==
+
-
Все главные угловые миноры A отличны от 0:
+
-
{|
+
-
|A<sub>1</sub> = a<sub>11</sub> &ne; 0
+
-
|;
+
-
|
+
-
{|style="text-align:center"
+
-
|rowspan="2"|A<sub>2</sub>&nbsp;=&nbsp;(
+
-
|a<sub>11</sub>
+
-
|a<sub>12</sub>
+
-
|rowspan="2"|)&nbsp;&ne;&nbsp;0
+
-
|-
+
-
|a<sub>21</sub>
+
-
|a<sub>22</sub>
+
-
|}
+
-
|;
+
-
|&hellip;;
+
-
|
+
-
{|style="text-align:center"
+
-
|rowspan="3"|A<sub>i</sub>&nbsp;=&nbsp;(
+
-
|a<sub>11</sub>
+
-
|...
+
-
|a<sub>1i</sub>
+
-
|rowspan="3"|)&nbsp;&ne;&nbsp;0
+
-
|-
+
-
|colspan="3"|...
+
-
|-
+
-
|a<sub>i1</sub>
+
-
|...
+
-
|a<sub>ii</sub>
+
-
|}
+
-
|}
+
-
 
+
-
== Связь метода Гаусса с разложением A = B &times; C ==
+
-
Три этапа метода Гаусса соответствуют трём этапам факторизации:
+
-
* В методе Гаусса для того, чтобы свести матрицу к верхнетреугольной матрице с единицами на главной диагонали, требуется <sup>(m<sup>3</sup>&nbsp;&minus;&nbsp;m)</sup>/<sub>3</sub> операций — то же количество действий требуется для нахождения матриц B и C
+
-
* Для решения уравнения By&nbsp;=&nbsp;f&nbsp; требуется <sup>m(m&nbsp;+&nbsp;1)</sup>/<sub>2</sub> действий — в точности то число действий, которое требуется для вычисления правой части в методе Гаусса
+
-
* Для решения уравнения Cx&nbsp;= &nbsp;y&nbsp; требуется <sup>m(m&nbsp;&minus;&nbsp;1)</sup>/<sub>2</sub> действий — в точности то число действий, которое требуется для обратного хода Гаусса
+
-
 
+
-
== Метод Гаусса-Жордана ==
+
-
'''Метод Гаусса-Жордана''':
+
-
* Обозначим A<sup>&minus;1</sup> = X. Тогда AX = E
+
-
* Запишем в явном виде:
+
-
* &sum;<sub>l = 1</sub><sup>m</sup>a<sub>il</sub>x<sub>lj</sub> = &delta;<sub>ij</sub>, i, j = 1..m
+
-
* m<sup>2</sup> неизвестных, поэтому действий m<sup>6</sup>
+
-
* Разумно организовав алгоритм, можно получить порядка m<sup>3</sup> действий
+
-
 
+
-
== Метод квадратного корня (метод Холецкого) ==
+
-
* Решаем уравнение Ax = f
+
-
* |A| &ne; 0 (m &times; m)
+
-
* A = A* &hArr; a<sub>ij</sub> = <span style="border-top:solid 1px">a<sub>ji</sub></span>
+
-
* A = A<sup>T</sup> &mdash; для вещественных матриц
+
-
 
+
-
Факторизуем матрицу A в виде A = S*DS
+
-
{|style="text-align:center"
+
-
|
+
-
|s<sub>11</sub>
+
-
|s<sub>12</sub>
+
-
|s<sub>13</sub>
+
-
|...
+
-
|s<sub>1m</sub>
+
-
|-
+
-
|
+
-
|0
+
-
|s<sub>22</sub>
+
-
|s<sub>23</sub>
+
-
|...
+
-
|s<sub>2m</sub>
+
-
|-
+
-
|S =
+
-
|0
+
-
|0
+
-
|s<sub>33</sub>
+
-
|..
+
-
|s<sub>3m</sub>
+
-
|-
+
-
|
+
-
|colspan="5"|...
+
-
|-
+
-
|
+
-
|0
+
-
|0
+
-
|0
+
-
|...
+
-
|s<sub>mm</sub>
+
-
|}
+
-
s<sub>ii</sub> > 0, i = <span style="border-top:solid 1px">2&hellip;m</span>
+
-
 
+
-
D = diag (d<sub>11</sub>, &hellip;, d<sub>mm</sub>) d<sub>ii</sub> = &plusmn;1, i = 1..m
+
-
 
+
-
Тогда система решается следующим образом:
+
-
* S*DSx = f
+
-
* S*Dy = f
+
-
* Sx = y
+
-
Эти две системы решаются явным образом, ибо матрицы треугольные.
+
-
 
+
-
== Достоинства и недостатки метода квадратного корня ==
+
-
Плюс:
+
-
* Количество действий сокращается в два раза (<sup>m<sup>3</sup></sup>/<sub>6</sub> умножений и делений + m извлечений корня)
+
-
Минусы:
+
-
* Только для эрмитовых матриц
+
-
 
+
-
== Что значит «решить СЛАУ итерационным методом» ==
+
-
* x<sub>i</sub><sup>n</sup> — i-я кордината, n-я итерация
+
-
* x<sup>0</sup> — начальное приближение
+
-
 
+
-
Далее организуется процесс так, что lim<sub>n &rarr; &infin;</sub>x<sup>n</sup> &rarr; x, то есть, в некоторой норме |x<sup>n</sup> &minus; x| &lt; &epsilon;, &epsilon; &gt; 0
+
-
 
+
-
== Вопросы, рассматриваемые при исследовании итерационного метода ==
+
-
* Будет ли сходиться. При каких параметрах и начальном приближении будет сходиться, при каких нет.
+
-
* С какой скоростью
+
-
 
+
-
== Метод Якоби ==
+
-
* x<sub>i</sub><sup>n + 1</sup> = <sup>f<sub>i</sub></sup>/<sub>a<sub>ii</sub></sub> &minus; &sum;<sub>j = 1</sub><sup>i &minus; 1</sup> <sup>a<sub>ij</sub></sup>/<sub>a<sub>ii</sub></sub>x<sub>j</sub><sup>n</sup> &minus; &sum;<sub>j = i + 1</sub><sup>m</sup> <sup>a<sub>ij</sub></sup>/<sub>a<sub>ii</sub></sub>x<sub>j</sub><sup>n</sup>, n &isin; ℕ &cup; {0}
+
-
* x<sup>0</sup> — задано
+
-
 
+
-
== Достоинства и недостатки метода Якоби ==
+
-
Плюс:
+
-
* Данный метод реализуется достаточно просто
+
-
Минус:
+
-
* Очень медленная сходимость
+
-
 
+
-
== Метод Зейделя ==
+
-
* x<sub>i</sub><sup>n + 1</sup> = <sup>f<sub>i</sub></sup>/<sub>a<sub>ii</sub></sub> &minus; &sum;<sub>j = 1</sub><sup>i &minus; 1</sup> <sup>a<sub>ij</sub></sup>/<sub>a<sub>ii</sub></sub>x<sub>j</sub><sup>n + 1</sup> &minus; &sum;<sub>j = i + 1</sub><sup>m</sup> <sup>a<sub>ij</sub></sup>/<sub>a<sub>ii</sub></sub>x<sub>j</sub><sup>n</sup>, n &isin; ℕ &cup; {0} (3)
+
-
* x<sup>0</sup> — задано
+
-
 
+
-
== Соотношение сложностей методов Якоби и Зейделя ==
+
-
По сложности и скорости сходимости эти два метода одинаковы.//А вот и неправда, Зейдель сходится быстрей, поскольку использует значения новой итерации
+
-
 
+
-
== Двуслойная запись ==
+
-
'''Двуслойная запись''' — когда связываются две соседние итерации.
+
-
 
+
-
== Каноническая форма записи двуслойного итерационного метода решения СЛАУ ==
+
-
'''Определение'''. Канонической формой записи двуслойного итерационного метода решения системы Ax = f, A (m &times; m), det A &ne; 0 называется его запись в виде:
+
-
* B<sub>n + 1</sub> <sup>(x<sup>n + 1</sup> &minus; x<sup>n</sup>)</sup>/<sub>&tau;<sub>n + 1</sub></sub> + Ax<sup>n</sup> = f (4)
+
-
где
+
-
* &tau;<sub>n + 1</sub> > 0, n &isin; ℕ &cup; {0}
+
-
* x<sup>0</sup> — задано
+
-
* &exist;B<sub>n + 1</sub><sup>&minus;1</sup>
+
-
 
+
-
== Виды итерационных методов ==
+
-
* Метод явный, если B<sub>n + 1</sub> = E. Если матрица диагональная, то тоже явный.
+
-
* Метод стационарный, если
+
-
** B<sub>n + 1</sub> = B
+
-
** &tau;<sub>n + 1</sub> = &tau;
+
-
 
+
-
== Метод простой итерации ==
+
-
'''Метод простой итерации (МПИ)''':
+
-
* (МПИ) (x<sup>n+1</sup> &minus; x<sup>n</sup>)/&tau; + Ax<sup>n</sup> = f, x<sup>0</sup> &mdash; задано, n &isin; ℕ &cup; {0}, &tau; > 0
+
-
* Если &tau; меняется, то это другой метод, для которого оптимален Чебышевский набор параметров.
+
-
 
+
-
== Попеременно-треугольный итерационный метод (метод Самарского) (ПТИМ) ==
+
-
* A = R<sub>1</sub> + R<sub>2</sub>, где R<sub>1</sub> — нижнетреугольная матрица с диагональными элементам r<sub>1<sub>ii</sub></sub> = a<sub>ii</sub>/2, R<sub>2</sub> — верхнетреугольная матрица с диагональными элементам r<sub>2<sub>ii</sub></sub> = a<sub>ii</sub>/2.
+
-
* (E + &omega;R<sub>1</sub>)(E + &omega;R<sub>2</sub>)((x<sup>n + 1</sup> &minus; x<sup>n</sup>)/&tau;) + Ax<sup>n</sup> = f (5)
+
-
** n &isin; ℕ &cup; {0}, x<sup>0</sup> задано, &omega; > 0, &tau; > 0
+
-
* Применительно к канонической записи B = (E + &omega;R<sub>1</sub>)(E + &omega;R<sub>2</sub>)
+
-
 
+
-
== Невязка ==
+
-
r<sup>n</sup> = f &minus; Ax<sup>n</sup>
+
-
 
+
-
== Энергетическая норма ==
+
-
'''Энергетическая норма''' ||x||<sub>D</sub>&nbsp;=&nbsp;(Dx,x)<sup><sup>1</sup>/<sub>2</sub></sup>, где D — положительно определённый опрератор, то есть (Dx,&nbsp;x)&nbsp;>&nbsp;0, &forall;&nbsp;x&nbsp;&ne;&nbsp;0.
+
-
 
+
-
== Вектор погрешности ==
+
-
'''Вектор погрешности''': v<sup>n</sup>&nbsp;=&nbsp;x<sup>n</sup>&nbsp;&minus;&nbsp;x.
+
-
 
+
-
== Матрица перехода ==
+
-
'''S = E &minus; &tau;B<sup>&minus;1</sup>A'''
+
-
 
+
-
Вывод:
+
-
* Ax = f
+
-
* &exist; A<sup>&minus;1</sup> (m &times; m)
+
-
* B <sup>(x<sup>n + 1</sup> &minus; x<sup>n</sup>)</sup>/<sub>&tau;</sub> + Ax<sup>n</sup> = f
+
-
* x<sup>n</sup>&nbsp;=&nbsp;v<sup>n</sup>&nbsp;+&nbsp;x
+
-
* B (v<sup>n&nbsp;+&nbsp;1</sup> &minus; v<sup>n</sup>)/&tau; + Av<sup>n</sup> = 0
+
-
* (v<sup>n&nbsp;+&nbsp;1</sup> &minus; v<sup>n</sup>)/&tau; + B<sup>&minus;1</sup>Av<sup>n</sup> = 0
+
-
* v<sup>n+1</sup> = v<sup>n</sup> &minus; &tau;B<sup>&minus;1</sup>Av<sup>n</sup> = (E &minus; &tau;B<sup>&minus;1</sup>A)v<sup>n</sup>
+
-
* S = E &minus; &tau;B<sup>&minus;1</sup>A
+
-
 
+
-
== Условие сходимости матрицы при любом начальном приближении, условие на матрицу перехода ==
+
-
'''Теорема 1'''. Итерационный метод B <sup>(x<sup>n + 1</sup> &minus; x<sup>n</sup>)</sup>/<sub>&tau;</sub> + Ax<sup>n</sup> = f решения системы Ax = f сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы S = E &minus; &tau;B<sup>&minus;1</sup>A по модулю меньше 1: |&lambda;<sub>k</sub><sup>S</sup>|&nbsp;<&nbsp;1.
+
-
 
+
-
Это означает, что оператор S — сжимающий.
+
-
 
+
-
== Достаточное условие сходимости итерационного метода (теорема Самарского) ==
+
-
'''Теорема (Самарского, о достаточном условии сходимости метода B <sup>(x<sup>n + 1</sup> &minus; x<sup>n</sup>)</sup>/<sub>&tau;</sub> + Ax<sup>n</sup> = f)'''. Пусть есть A&nbsp;=&nbsp;A*&nbsp;=&nbsp;A<sup>T</sup>&nbsp;>&nbsp;0 (симметрический положительно определённый оператор (матрица)) и выполненно операторное (матричное) неравенство B &minus; 0,5&tau;A&nbsp;>&nbsp;0, &tau;&nbsp;>&nbsp;0. Тогда итерационный метод сходится при любом начальном приближении в среднеквадратичной норме ||x<sup>n</sup>&nbsp;&minus;&nbsp;x||&nbsp;=&nbsp;(&sum;<sub>i = 1</sub><sup>m</sup> (x<sub>i</sub><sup>n</sup>&nbsp;&minus;&nbsp;xi)<sup>2</sup>)<sup><sup>1</sup>/<sub>2</sub></sup>&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;<sub>2</sub> = max<sub>1 &le; x &le; m</sub>&lambda;<sub>k</sub><sup>A</sup> > 0. Тогда 0 < &tau; < 2/&gamma;<sub>2</sub> МПИ сходится при &forall;&nbsp;x<sup>0</sup>
+
-
 
+
-
== Теорема о сходимости метода Зейделя ==
+
-
'''Следствие 4'''. Пусть &exist; A&nbsp;=&nbsp;A*&nbsp;>&nbsp;0, 2D&nbsp;>&nbsp;A. Тогда метод Зейделя сходится при любом начальном приближении в среднеквадратичной норме.
+
-
Вообще достаточно только самосопряженности оператора А: A&nbsp;=&nbsp;A*&nbsp;>&nbsp;0
+
-
 
+
-
== Скорость сходимости итерационного метода ==
+
-
ln <sup>1</sup>/<sub>&rho;</sub> — '''скорость сходимости итерационного метода'''
+
-
 
+
-
== Оценка скорости сходимости итерационного метода ==
+
-
'''Теорема (об оценке скорости сходимости итерационного метода)'''. Пусть
+
-
* A = A* > 0
+
-
* B = B* > 0
+
-
* 0 &lt; &rho; &lt; 1
+
-
* <sup>1 &minus; &rho;</sup>/<sub>&tau;</sub>B &le; A &le; <sup>1 + &rho;</sup>/<sub>&tau;</sub>B
+
-
Тогда итерационный метод B <sup>(x<sup>n + 1</sup> &minus; x<sup>n</sup>)</sup>/<sub>&tau;</sub> + Ax<sup>n</sup> = f сходится к решению СЛАУ Ax = f и имеет место оценка ||v<sup>n + 1</sup>||<sub>B</sub> &le; &rho;||v<sup>n</sup>||
+
-
 
+
-
== Равенство Парсеваля ==
+
-
'''Равенство Парсеваля'''
+
-
Пусть D&nbsp;=&nbsp;D*&nbsp;>&nbsp;0, &exist; ортонормированный базис из собственных векторов x&nbsp;=&nbsp;&sum;<sub>k&nbsp;=&nbsp;1</sub><sup>m</sup>c<sub>k</sub>e<sub>k</sub>.
+
-
 
+
-
Тогда равенство Парсиваля есть ||x||<sup>2</sup>&nbsp;=&nbsp;&sum;<sub>k&nbsp;=&nbsp;1</sub><sup>m</sup>c<sub>k</sub><sup>2</sup>
+
-
 
+
-
== Оценка скорости сходимости МПИ ==
+
-
'''Следствие 2 из теоремы об оценке скорости сходимости итерационного метода.''' Пусть A = A* > 0,
+
-
* &gamma;<sub>1</sub> = min<sub>1 &le; k &le; m</sub> &lambda;<sub>k</sub><sup>A</sup>, > 0 в силу положительной определённости
+
-
* &gamma;<sub>2</sub> = max<sub>1 &le; k &le; m</sub> &lambda;<sub>k</sub><sup>A</sup>
+
-
 
+
-
Тогда МПИ (x<sup>n+1</sup> &minus; x<sup>n</sup>)/&tau; + Ax<sup>n</sup> = f, где &tau; = <sup>2</sup>/<sub>&gamma;<sub>1</sub> + &gamma;<sub>2</sub></sub>, &rho; = <sup>1 &minus; &xi;</sup>/<sub>1 + &xi;</sub>, &xi; = <sup>&gamma;<sub>1</sub></sup>/<sub>&gamma;<sub>2</sub></sub> — сходится, имеет место оценка ||x<sup>n+1</sup> &minus; x|| &le; &rho;||x<sup>n</sup> &minus; x||
+
-
 
+
-
== Теорема о сходимости ПТИМ ==
+
-
'''Теорема (о сходимости ПТИМ)'''. Пусть A = A* > 0, &omega; > <sup>&tau;</sup>/<sub>4</sub>. Тогда ПТИМ сходится в среднеквадратичной норме при любом начальном приближении.
+
-
 
+
-
== Теорема об оценке скорости сходимости ПТИМ ==
+
-
'''Теорема (об оценке скорости сходимости ПТИМ)'''. Пусть A = A* > 0. Пусть существуют такие две константы &delta; > 0, &Delta; > 0:
+
-
* A &ge; &delta;E, R<sub>2</sub>*R<sub>2</sub> &le; <sup>&Delta;</sup>/<sub>4</sub> A (2)
+
-
* Положим &omega; = <sup>2</sup>/<sub>√<span style="border-top:solid 1px">&delta;&Delta;</span></sub>, &tau; = <sup>2</sup>/<sub>&gamma;<sub>1</sub> + &gamma;<sub>2</sub></sub>, &gamma;<sub>1</sub> = <sup>√<span style="border-top:solid 1px">&delta;</span></sup>/<sub>2</sub> (<sup>√<span style="border-top:solid 1px">&delta;&Delta;</span></sup>/<sub>√<span style="border-top:solid 1px">&delta;</span>+√<span style="border-top:solid 1px">&Delta;</span></sub>); &gamma;<sub>2</sub> = <sup>√<span style="border-top:solid 1px">&delta;&Delta;</span></sup>/<sub>4</sub>
+
-
* ||x<sup>n + 1</sup> &minus; x||<sub>B</sub> &le; &rho; ||x<sup>n</sup> &minus; x||<sub>B</sub>
+
-
* где B = (E + &omega;R<sub>2</sub>*)(E + &omega;R<sub>2</sub>), &rho; = <sup>1 &minus; √<span style="border-top:solid 1px">&eta;</span></sup>/<sub>1 + 3√<span style="border-top:solid 1px">&eta;</span></sub>, &eta; = <sup>&delta;</sup>/<sub>&Delta;</sub>
+
-
** R<sub>2</sub>* = R<sub>1</sub>
+
-
 
+
-
== Оценка скорости сходимости для метода простой итерации ==
+
-
* ||x<sup>n + 1</sup> &minus; x|| &le; &rho; ||x<sup>n</sup> &minus; x||, &rho; = <sup>1 &minus; &xi;</sup>/<sub>1 + &xi;</sub>, &xi; = <sup>&gamma;<sub>1</sub></sup>/<sub>&gamma;<sub>2</sub></sub>, &xi; = &eta; = O(m<sup>&minus;2</sup>)
+
-
* 1/&rho; = <sup>1 + &eta;</sup>/<sub>1 &minus; &eta;</sub> &asymp; (1 + &eta;)<sup>2</sup> &asymp; 1 + 2&eta;
+
-
* ln <sup>1</sup>/<sub>&rho;</sub> &asymp; &eta;, n<sub>0</sub>(&epsilon;) = O(m<sup>2</sup>)
+
-
 
+
-
== Задача на собственные значения ==
+
-
Есть совершенно произвольная вещественная матрица A. Нужно найти &lambda; такие, что Ax = &lambda;x, x &ne; 0 (1)
+
-
* &lambda; — собственные значения
+
-
* x — собственные вектора
+
-
 
+
-
Два круга проблем:
+
-
* Частичная проблема собственных значений — нужно находить только отдельные собственные значения (максимальное, минимальное)
+
-
* Полная проблема собственных значений — нужно находить все собственные значения
+
-
 
+
-
Всего m значений (с учётом кратности): &lambda;<sub>k</sub>, k = 1..m
+
-
 
+
-
Вообще говоря, собственные значения комплексные.
+
-
 
+
-
Все методы итерационные. Один из самых простых методов — степенной метод.
+
-
 
+
-
== Степенной метод нахождения собственных значений ==
+
-
'''Степенной метод''' — метод, который описывается уравнением 1:
+
-
* x<sub>n + 1</sub> = Ax<sub>n</sub> (1)
+
-
* n = 0, 1, ..., x<sub>0</sub> — начальное приближение
+
-
* x<sub>n</sub> = A<sub>n</sub>x<sub>0</sub>
+
-
 
+
-
== Условия для степенного метода ==
+
-
* Предположения относительно матрицы A:
+
-
** Все собственные значения расположены в порядке неубывания модуля: |&lambda;<sub>1</sub>| &le; |&lambda;<sub>2</sub>| &le; |&lambda;<sub>3</sub>| &le; ... &le; |&lambda;<sub>m</sub>|
+
-
** Условие А: Мы рассматриваем класс матриц, для которфых существет базис из собственных векторов: {e<sub>k</sub>}<sub>1</sub><sup>m</sup> — базис из собственных векторов A (Ae<sub>k</sub> = &lambda;<sub>k</sub>e<sub>k</sub>, k = 1..m)
+
-
** Ограничение B: последнее собственное значение не является кратным: |(&lambda;<sub>m &minus; 1</sub>)/(&lambda;<sub>m</sub>) < 1
+
-
** Ограничение C: &forall; x = c<sub>1</sub>e<sub>1</sub> + ... + c<sub>m</sub>e<sub>m</sub>, c<sub>m</sub> &ne; 0
+
-
 
+
-
== Метод обратных итераций ==
+
-
# &exist; A<sup>&minus;1</sup>. тогда нулевых собственных значений нет Кроме того, у обратной матрицы СЗ обратны к СЗ исходной матрицы. Тогда:
+
-
#* Ax<sub>n + 1</sub> = x<sub>n</sub>, n = 0, 1, &hellip;, x<sub>0</sub> — начальное приближение (3) Этот метод неявный. Перепишем его как:
+
-
#* x<sub>n + 1</sub> = A<sup>&minus;1</sup>x<sub>n</sub> (4)
+
-
#* x<sub>n</sub> = (A<sup>&minus;1</sup>)<sup>n</sup>x<sub>n</sub>
+
-
 
+
-
Условия:<br />
+
-
A) &exist; {e<sub>k</sub>}<sub>1</sub><sup>m</sup> из СВ<br />
+
-
B) |&lambda;<sub>1</sub>/&lambda;<sub>2</sub>| < 1<br />
+
-
C) x<sub>0</sub> = c<sub>1</sub>e<sub>1</sub>+ &hellip; + c<sub>m</sub>e<sub>m</sub>, c<sub>1</sub> &ne; 0
+
-
 
+
-
Тогда:
+
-
* x<sub>n</sub> = c<sub>1</sub>&lambda;<sub>1</sub><sup>&minus;n</sup>e<sub>1</sub>+ &hellip; + c<sub>m</sub>&lambda;<sub>m</sub><sup>&minus;n</sup>e<sub>m</sub>
+
-
* x<sub>n</sub>/e<sub>1</sub>&lambda;<sub>1</sub><sup>&minus;n</sup> = e<sub>1</sub> + &hellip; + (c<sub>m</sub>/c<sub>1</sub>)(&lambda;<sub>1</sub>/&lambda;<sub>m</sub>)<sup>n</sup>e<sub>m</sub>
+
-
 
+
-
== Метод обратных итераций со сдвигом ==
+
-
* (A &minus; &alpha;E)x<sub>n + 1</sub> = x<sub>n</sub> (5)
+
-
** n = 0, 1, &hellip;, x<sub>0</sub> — начальное приближение, &alpha; &isin; R
+
-
* &exist; (A &minus; &alpha;E)<sup>&minus;1</sup>
+
-
* x<sub>n + 1</sub> = (A &minus; &alpha;E)<sup>&minus;1</sup>x<sub>n</sub>
+
-
* x<sub>n</sub> = e<sub>l</sub>
+
-
* 1/|&lambda;<sub>l</sub> &minus; &alpha;| = max<sub>1 &le; k &le; m</sub> 1/|&lambda;<sub>k</sub> &minus; &alpha;|
+
-
 
+
-
== Что такое верхняя почти треугольная форма ==
+
-
Верхняя почти треугольная форма — форма, у которой обе побочных диагонали от главной ненулевые, а дальше треугольник из нулей.
+
-
 
+
-
== Преобразование элементарных отражений (преобразование Хаусхолдера) ==
+
-
'''Определение'''. Преобразование элементарных отражений (Преобразование Хаусхолдера).
+
-
Элементарным отражением, соответствующим данному вектору v называется преобразование, задаваемое матрицей: H = E &minus; 2 vv<sup>T</sup>/||v||<sup>2</sup>
+
-
 
+
-
== QR-алгоритм решения полной проблемы собственных значений ==
+
-
 
+
-
&forall; A = Q &times; R, Q<sup>&minus;1</sup> = Q<sup>T</sup>, R — верхнетреугольная матрица. Любую матрицу можно представить в виде данного разложения.
+
-
 
+
-
== Количество действий для работы QR-алгоритма ==
+
-
* полная — O(m<sup>3</sup>)
+
-
* ВПТФ — O(m<sup>2</sup>)
+
-
* А - трехдиагональная - O(m)
+
-
 
+
-
== Теорема о сохранении ВПТФ ==
+
-
Пусть C = B &times; A, B — ВТФ, A — ВПТФ. Тогда C — ВПТФ.
+
-
 
+
-
= Глава 2 =
+
-
== Задача интерполяции ==
+
-
Суть задачи: есть отрезок x &isin; [a, b]. Мы разбиваем его несовпадающими узлами a &le; x<sub>0</sub> &lt; x<sub>1</sub> &lt; x<sub>2</sub> &lt; &hellip; &lt; x<sub>n</sub> &le; b — {x<sub>i</sub>}<sub>0</sub><sup>n</sup> — узлы интерполирование (n + 1 штук). Есть f(x<sub>i</sub>) = f<sub>i</sub>, i = 0&hellip;n. Если полином P<sub>n</sub>(x) = a<sub>0</sub> + a<sub>1</sub>x + &hellip; a<sub>n</sub>x<sup>n</sup> такой, что P<sub>n</sub>(x<sub>i</sub>) = f(x<sub>i</sub>), i = 0&hellip;n (1), то данный полином называется интерполяционным для f (интерполирует f).
+
-
 
+
-
== Интерполяционный полином ==
+
-
Если полином P<sub>n</sub>(x) = a<sub>0</sub> + a<sub>1</sub>x + &hellip; a<sub>n</sub>x<sup>n</sup> такой, что P<sub>n</sub>(x<sub>i</sub>) = f(x<sub>i</sub>), i = 0&hellip;n (1), то данный полином называется '''интерполяционным''' для f (интерполирует f).
+
-
 
+
-
== Существование и единственность интерполяционного полинома ==
+
-
При условиях, накладываемых в постановке задачи интерполяции (узлы интерполирования не совпадают) интерполяционный полином существует и единственный.
+
-
 
+
-
== Интерполяционный полином в форме Лагранжа ==
+
-
L<sub>n</sub>(x) = &sum;<sub>k = 0</sub><sup>n</sup>(&omega;(x))/((x &minus;x<sub>k</sub>)&omega;'(x<sub>k</sub>)) &times; f(x<sub>k</sub>), где
+
-
* &omega;(x) = (x &minus; x<sub>0</sub>)(x &minus; x<sub>1</sub>)&hellip;(x &minus; x<sub>n</sub>) = &prod;<sub>i = 0</sub><sup>n</sup>(x<sub>i</sub> &minus; x<sub>j</sub>)
+
-
* &omega;(x) = [ ](x &minus; x<sub>k</sub>)
+
-
* &omega;'(x) = [ ] + [ ]'(x &minus; x<sub>k</sub>)
+
-
* &omega;'(x<sub>k</sub>) = &prod;<sub>k &ne; j</sub><sup>n</sup>(x<sub>k</sub> &minus; x<sub>j</sub>)
+
-
 
+
-
== Определение погрешности интерполяционного полинома ==
+
-
Погрешность интерполяционной формулы Лагранжа &psi;<sub>L<sub>n</sub></sub>(x) = f(x) &minus; L<sub>n</sub>(x). Во всех узлах она будет совпадать: &psi;<sub>L<sub>n</sub></sub>(x<sub>i</sub>) = 0.
+
-
 
+
-
'''Замечание 1'''. Если f(x) — полином степени &le; n, то полином Лагранжа даёт точное приближение, то есть погрешность тождественно равна 0.
+
-
 
+
-
'''Замечание 2'''. По большому числу узлов интерполяцию проводят крайне редко. Можно подобрать узлы так, что при увеличении количества узлов сходимости не будет.
+
-
 
+
-
== Разделённая разность ==
+
-
 
+
-
'''Разделённой разностью первого порядка''', построенной по узлам x<sub>i</sub>, x<sub>j</sub> называется отношение f(x<sub>i</sub>, x<sub>j</sub>) = (f(x<sub>j</sub>) &minus; f(x<sub>i</sub>)/(x<sub>j</sub> &minus; x<sub>i</sub>))
+
-
 
+
-
'''Разделённая разность k+1-го порядка''': пусть есть f(x<sub>j</sub>, x<sub>j + 1</sub>, &hellip;, x<sub>j + k</sub>), f(x<sub>j + 1</sub>, x<sub>j + 2</sub>, &hellip;, x<sub>j + k + 1</sub>) — разности k-го порядка. Тогда f(x<sub>j</sub>, x<sub>j + 1</sub>, &hellip;, x<sub>j + k + 1</sub>) = (f(x<sub>j + 1</sub>, x<sub>j + 2</sub>, &hellip;, x<sub>j + k + 1</sub>) &minus; f(x<sub>j</sub>, x<sub>j + 1</sub>, &hellip;, x<sub>j + k</sub>))/(x<sub>j + k + 1</sub> &minus; x<sub>j</sub>) — разделённая разность k + 1-го порядка.
+
-
 
+
-
== Выражение разделённой разности через значения функции в точках ==
+
-
Разделённая разность k-го порядка, построенная по узлам x<sub>0</sub>, &hellip; x<sub>k</sub> может быть записана как f(x<sub>0</sub>, x<sub>1</sub>, &hellip;, x<sub>k</sub>) = &sum;<sub>i = 0</sub><sup>k</sup>(f(x<sub>i</sub>))/(&omega;<sub>0, k</sub>'(x<sub>i</sub>))
+
-
 
+
-
== Выражение разделённой разности через значение функции в 0-м узле и разделённую разность k-го порядка ==
+
-
f(x<sub>k</sub>) = f(x<sub>0</sub>) + (x<sub>k</sub> &minus; x<sub>0</sub>)f(x<sub>0</sub>, x<sub>1</sub>) + (x<sub>k</sub> &minus; x<sub>0</sub>)(x<sub>k</sub> &minus; x<sub>1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, x<sub>2</sub>) + &hellip; + (x<sub>k</sub> &minus; x<sub>0</sub>)(x<sub>k</sub> &minus; x<sub>1</sub>)&hellip;(x<sub>k</sub> &minus; x<sub>k &minus; 1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, &hellip;, x<sub>k</sub>)
+
-
 
+
-
== Интерполяционная функция в форме Ньютона ==
+
-
N<sub>n</sub>(x) = f(x<sub>0</sub>) + (x &minus; x<sub>0</sub>)f(x<sub>0</sub>, x<sub>1</sub>) + (x &minus; x<sub>0</sub>)(x &minus; x<sub>1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, x<sub>2</sub>) + &hellip; + (x &minus; x<sub>0</sub>)(x &minus; x<sub>1</sub>)&hellip;(x &minus; x<sub>n &minus; 1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, &hellip;, x<sub>n</sub>)
+
-
 
+
-
== Погрешность интерполяционной формулы Ньютона ==
+
-
Погрешность та же самая, но записана внешне по-другому:
+
-
 
+
-
|&psi;<sub>N<sub>n</sub></sub>(x)| = |f(x) &minus; N<sub>n</sub>(x)| &le; M<sub>n + 1</sub>/(n + 1)! &times; |&omega;(x)|, M<sub>n + 1</sub> = sup<sub>a &le; x&le; b</sub> |f(x)<sup>(n + 1)</sup>|
+
-
 
+
-
== Когда лучше использовать Ньютона, а когда — Лагранжа
+
-
* Ньютон удобен при постепенном добавлении узлов, когда их количество не фиксировано
+
-
* Лагранж удобен, когда количество узлов фиксировано, но они могут находиться в разных местах
+
-
 
+
-
== Интерполяционная формула Эрмита ==
+
-
Пусть у нас есть узлы x<sub>0</sub>, &hellip; x<sub>m</sub> — m + 1 узел. Информация в узлах такая: в узле может быть задано значение производных:
+
-
{|
+
-
|x<sub>0</sub>
+
-
|x<sub>1</sub>
+
-
|&hellip;
+
-
|x<sub>m</sub>
+
-
|-
+
-
|f(x<sub>0</sub>)
+
-
|f(x<sub>1</sub>)
+
-
|&hellip;
+
-
|f(x<sub>m</sub>)
+
-
|-
+
-
|f'(x<sub>0</sub>)
+
-
|f'(x<sub>1</sub>)
+
-
|&hellip;
+
-
|f'(x<sub>m</sub>)
+
-
|-
+
-
|&hellip;
+
-
|-
+
-
|f<sup>(a<sub>0</sub> &minus; 1)</sup>(x<sub>0</sub>)
+
-
|f<sup>(a<sub>1</sub> &minus; 1)</sup>(x<sub>1</sub>)
+
-
|&hellip;
+
-
|f<sup>(a<sub>m</sub> &minus; 1)</sup>(x<sub>m</sub>)
+
-
|}
+
-
 
+
-
* a<sub>i</sub> &isin; N ( натуральное), i = 0&hellip;m
+
-
* a<sub>i</sub> — кратность i-го узла
+
-
 
+
-
Цель: построить H<sub>n</sub>(x)
+
-
 
+
-
Замечание. H<sub>n</sub><sup>(i)</sup> = f<sup>(i)</sup>(x<sub>k</sub>), k = 0&hellip;m, i = 0&hellip;a<sub>k</sub> &minus; 1 (1)
+
-
 
+
-
При выполнении условия a<sub>0</sub> + a<sub>1</sub> + &hellip; + a<sub>m</sub> = n + 1 мы можем построить полином Эрмита, причём единственный.
+
-
 
+
-
== Общий вид полинома Эрмита ==
+
-
H<sub>n</sub>(x) = &sum;<sub>k = 0</sub><sup>m</sup> &sum;<sub>i = 0</sub><sup>a<sub>k</sub> &minus; 1</sup> c<sub>k, i</sub>(x)f<sup>(i)</sup>(x<sub>k</sub>)
+
-
* c<sub>k, i</sub>(x) — полином n-й степени
+
-
* x<sub>i</sub> — различные
+
-
 
+
-
== H<sub>3</sub>(x) ==
+
-
H<sub>3</sub>(x) = c<sub>0</sub>(x)f(x<sub>0</sub>) + c<sub>1</sub>(x)f(x<sub>1</sub>) + c<sub>2</sub>(x)f(x<sub>2</sub>) + b<sub>1</sub>(x)f'(x<sub>1</sub>)
+
-
* c<sub>0</sub>(x) = ((x &minus; x<sub>1</sub>)<sup>2</sup>(x &minus; x<sub>2</sub>))/((x<sub>0</sub> &minus; x<sub>1</sub>)<sup>2</sup>(x<sub>0</sub> &minus; x<sub>2</sub>))
+
-
* c<sub>2</sub>(x) = ((x &minus; x<sub>1</sub>)<sup>2</sup>(x &minus; x<sub>0</sub>))/((x<sub>2</sub> &minus; x<sub>1</sub>)<sup>2</sup>(x<sub>2</sub> &minus; x<sub>0</sub>))
+
-
* b<sub>1</sub>(x) = ((x &minus; x<sub>0</sub>)(x &minus; x<sub>1</sub>)(x &minus; x<sub>2</sub>))/((x<sub>1</sub> &minus; x<sub>0</sub>)(x<sub>1</sub> &minus; x<sub>2</sub>))
+
-
* c<sub>1</sub>(x) = (x &minus; x<sub>0</sub>)(x &minus; x<sub>2</sub>)/((x<sub>1</sub> &minus; x<sub>0</sub>)<sup>2</sup>(x<sub>1</sub> &minus; x<sub>2</sub>)<sup>2</sup>)) &times; [1 &minus; ((x &minus; x<sub>1</sub>)(2x<sub>1</sub> &minus; x<sub>0</sub> &minus; x<sub>2</sub>))/((x<sub>1</sub> &minus; x<sub>0</sub>)(x<sub>1</sub> &minus; x<sub>2</sub>))]
+
-
 
+
-
== Погрешность полинома Эрмита ==
+
-
* &psi;<sub>H<sub>3</sub></sub>(x) = f(x) &minus; H<sub>3</sub>(x) = f<sup>(4)</sup>(&xi;)/4!
+
-
* M<sub>4</sub> = sup<sub>x<sub>0</sub> &le; x &le; x<sub>2</sub></sub> |f<sup>(4)</sup>(x)|
+
-
* |f(x) &minus; H<sub>3</sub>(x)| &le; M<sub>4</sub>/4! &times; |&omega;(x)|
+
-
 
+
-
== Формула Симпсона ==
+
-
Пусть требуется найти ∫<sub>a</sub><sup>b</sup> f(x)dx, f(x<sub>i</sub>) = f<sub>i</sub>, f(x<sub>i</sub>+0,5h) = f<sub>i + 1/2</sub>
+
-
 
+
-
По формуле Симпсона:
+
-
* ∫<sub>x<sub>i &minus; 1</sub></sub><sup>x<sub>i</sub></sup> f(x)dx &asymp; h/6 &times; (f<sub>i &minus; 1</sub> + 4f<sub>i &minus; 1/2</sub> + f<sub>i</sub>)
+
-
 
+
-
== Оценка погрешности формулы Симпсона ==
+
-
* M<sub>4</sub> = sup<sub>a &le; x &le; b</sub> |f<sup>(4)</sup>(x)|
+
-
* &Psi;<sub>h</sub>(f) &le; (h/2)<sup>4</sup> (M<sub>4</sub>(b &minus; a))/180 = O(h<sup>4</sup>)
+
-
 
+
-
== L<sub>2</sub> для функций ==
+
-
Пусть задан отрезок [a, b]. Рассматривается множество функций таких, что ∫<sub>a</sub><sup>b</sup> f<sup>2</sup>(x)dx &lt; &infin;, f &isin; L<sub>2</sub>. В этом функциональном пространстве вводим векторное произведение: &forall; f, g &isin; L<sub>2</sub>: (f, g) = &int;<sub>a</sub><sup>b</sup> f(x)g(x)dx. Норма: ||f|| = (f, f)<sup>1/2</sup> = (&int;<sub>a</sub><sup>b</sup> f<sup>2</sup>(x)dx)<sup>1/2</sup>. Эта норма не согласована с нормой в дискретном L<sub>2</sub>.
+
-
 
+
-
== Наилучшее среднеквадратичное приближение ==
+
-
* Требуется найти такой обобщённый многочлен <span style="border-top:solid 1px">&phi;</span>(x) = &sum;<sub>k = 0</sub><sup>n</sup> c_<sub>k</sub>&phi;<sub>k</sub>(x), что
+
-
** ||f &minus; <span style="border-top:solid 1px">&phi;</span>(x)|| = &int;<sub>a</sub><sup>b</sup> (f(x) &minus; <span style="border-top:solid 1px">&phi;</span>(x))<sup>2</sup>dx = min<sub>&phi;(x)</sub>||f &minus; &phi;(x)||<sub>L<sub>2</sub></sub><sup>2</sup>
+
-
 
+
-
== Отклонение ==
+
-
&int;<sub>a</sub><sup>b</sup> (f(x) &minus; &sum;<sub>k = 0</sub><sup>n</sup> c<sub>k</sub>&phi;<sub>k</sub>(x))<sup>2</sup>dx = &int;<sub>a</sub><sup>b</sup> f(x)<sup>2</sup>dx &minus; 2&sum;<sub>k = 0</sub><sup>n</sup> c<sub>k</sub> &int;<sub>a</sub><sup>b</sup> f(x)&phi;<sub>0</sub>(x)dx + &sum;<sub>l = 0</sub><sup>n</sup> c<sub>l</sub> &sum;<sub>k = 0</sub><sup>n</sup> c<sub>k</sub> &int;<sub>a</sub><sup>b</sup> &phi;<sub>0</sub><sup>2</sup>(x)dx = &int;<sub>a</sub><sup>b</sup> f(x)<sup>2</sup>dx &minus; &sum;<sub>k = 0</sub><sup>n</sup> c<sub>k</sub><sup>2</sup> &ge; 0
+
-
* &sum;<sub>k = 0</sub><sup>n</sup> c<sub>k</sub><sup>2</sup> &le; ||f||<sup>2</sup> — неравенство Бесселя
+
-
* &sum;<sub>k = 0</sub><sup>n</sup> c<sub>k</sub><sup>2</sup> = ||f||<sup>2</sup> — равенство Парсеваля
+
-
 
+
-
= Глава 3 =
+
-
== Нелинейная система ==
+
-
{|
+
-
|rowspan = "4"|{
+
-
|f<sub>1</sub>(x<sub>1</sub>, x<sub>2</sub>, &hellip;, x<sub>m</sub>) = 0
+
-
|-
+
-
|f<sub>2</sub>(x<sub>1</sub>, x<sub>2</sub>, &hellip;, x<sub>m</sub>) = 0
+
-
|-
+
-
|&hellip;
+
-
|-
+
-
|f<sub>m</sub>(x<sub>1</sub>, x<sub>2</sub>, &hellip;, x<sub>m</sub>) = 0
+
-
|}
+
-
 
+
-
* f: R<sub>m</sub> &rarr; R<sub>m</sub>
+
-
* f_ = (f<sub>1</sub>, &hellip;, f<sub>m</sub>)<sup>T</sup>
+
-
* x_ = (x<sub>1</sub>, &hellip;, x<sub>m</sub>)<sup>T</sup>
+
-
* f_ (x_) = 0
+
-
 
+
-
== Задачи связанные с решением нелинейных уравнений и систем ==
+
-
# Локализация корня x<sub>*</sub>, f(x<sub>*</sub>) = 0, указать область, где он находится. Этим мы заниматься не будем
+
-
# Строится итерационный процесс, и аккуратно выбирая начальное приближение x<sub>0</sub> из локализованной области, x<sub>n</sub> &rarr; x<sub>*</sub>, n &rarr; &infin;
+
-
 
+
-
== Метод бисекции решения нелинейного уравнения ==
+
-
Второй метод более регулярный и он называется метод бисекции.
+
-
* f(a) < 0
+
-
* f(b) > 0
+
-
* Берётся x<sub>0</sub> = (a + b)/2
+
-
* Если f(x<sub>0</sub>) > 0, то x<sub>*</sub> &isin; (a, x<sub>0</sub>)
+
-
Каждый раз мы сужаем в два раза промежуток, где находится корень
+
-
 
+
-
== Метод простой итерации (МПИ) ==
+
-
* f(x) = 0 (1)
+
-
* x<sub>*</sub> &isin; U<sub>a</sub>(x<sub>*</sub>) (по определению)
+
-
* x = S(x) (2)
+
-
* x<sub>n + 1</sub> = S(x<sub>n</sub>) (3)
+
-
* x<sub>0</sub> &isin;(x<sub>*</sub>)
+
-
 
+
-
S(x) выбирается следующим образом: S(x) = x + r(x)f(x) (4). Единственное требование на r(x): sign(r(x)) &ne; 0 при x &isin; U<sub>a</sub>(x<sub>*</sub>).
+
-
 
+
-
== Условие наличия корня в отрезке при использовании МПИ ==
+
-
Если известно, что &exist; S'(x), и sup<sub>x &isin; U<sub>a</sub>(x<sub>*</sub>)</sub> |S'(x)| = q &lt; 1, то МПИ сходится, x<sub>0</sub> &isin; U<sub>a</sub>(x<sub>*</sub>)
+
-
 
+
-
== Специальный вид МПИ ==
+
-
(x<sub>n + 1</sub> &minus; x<sub>n</sub>)/&tau; + f(x<sub>n</sub>) = 0, &tau; &gt; 0, x<sub>0</sub> &isin; U<sub>a</sub>(x<sub>*</sub>), n = 0, 1, 2, &hellip;
+
-
 
+
-
== Границы выбора &tau; для МПИ, записанного в специальном виде для сходимость со скоростью геометрической прогрессии ==
+
-
&minus;1 &lt; 1 &minus; &tau;f'(x) &lt; 1 &rArr; 0 &lt; &tau; &lt; 2/M<sub>1</sub>
+
-
 
+
-
== Метод Эйткена ==
+
-
Предположим, что x<sub>n</sub> &minus; x<sub>*</sub> = Aq<sup>n</sup> (6). Запишем три итерации:
+
-
* x<sub>n &minus; 1</sub> &minus; x<sub>*</sub> = Aq<sup>n &minus; 1</sup> (7)
+
-
* x<sub>n</sub> &minus; x<sub>*</sub> = Aq<sup>n</sup> (8)
+
-
* x<sub>n + 1</sub> &minus; x<sub>*</sub> = Aq<sup>n +1</sup> (9)
+
-
Тогда:
+
-
* x<sub>*</sub> = x<sub>n</sub> &minus; ((x<sub>n + 1</sub> &minus; x<sub>n</sub>)<sup>2</sup>)/(x<sub>n + 1</sub> &minus; 2x<sub>n</sub> + x<sub>n &minus; 1</sub>)
+
-
Но так как (6) неточно, то это оказывается хоть и достаточно точным, но приближением.
+
-
 
+
-
== Метод Ньютона (касательных) ==
+
-
* f(x) = 0
+
-
* x<sub>*</sub> &isin; U<sub>a</sub>(x<sub>*</sub>) (по определению)
+
-
* x<sup>n</sup> — n-я итерация
+
-
* x<sup>n + 1</sup> = x<sup>n</sup> &minus; f(x<sup>n</sup>)/f'(x<sup>n</sup>), n = 0, 1, &hellip;, x<sup>0</sup> — начальное приближение (2)
+
-
* От функции требуется гладкость до третьей производной
+
-
Метод Ньютона очень быстро сходится, но он может зацикливаться.
+
-
 
+
-
== Модифицированный метод Ньютона ==
+
-
* x<sup>n + 1</sup> = x<sup>n</sup> &minus; f(x<sup>n</sup>)/f'(x<sup>0</sup>), n = 0, 1, &hellip;, x<sup>0</sup> — начальная итерация
+
-
* Скорость сходимости колеблется, но производительность повышается (особенно в системах) и позволяет избежать зацикливания
+
-
 
+
-
== Метод Ньютона для системы из 2 уравнений ==
+
-
{|
+
-
|rowspan= "2"|{
+
-
|f<sub>1</sub>(x<sub>1</sub>, x<sub>2</sub>) = 0
+
-
|rowspan="2"| (3)
+
-
|-
+
-
|f<sub>2</sub>(x<sub>1</sub>, x<sub>2</sub>) = 0
+
-
|}
+
-
 
+
-
(x<sub>1</sub><sup>*</sup>, x<sub>2</sub><sup>*</sup>) — решение
+
-
 
+
-
{|
+
-
|rowspan= "2"|J(x) = (
+
-
|(&delta;f<sub>1</sub>/&delta;x<sub>1</sub>)(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>)
+
-
|(&delta;f<sub>1</sub>/&delta;x<sub>2</sub>)(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>)
+
-
|rowspan= "2"|)
+
-
|-
+
-
|(&delta;f<sub>2</sub>/&delta;x<sub>1</sub>)(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>)
+
-
|(&delta;f<sub>2</sub>/&delta;x<sub>2</sub>)(x<sub>1</sub><sup>n</sup>, x<sub>2</sub><sup>n</sup>)
+
-
|}
+
-
 
+
-
* &exist; J<sup>&minus;1</sup>(x<sup>n</sup>)
+
-
* x<sup>n + 1</sup> = x<sup>n</sup> &minus; J<sup>&minus;1</sup>(x<sup>n</sup>)f(x<sup>n</sup>), n = 0, 1, &hellip;, x<sup>0</sup> &isin; U<sub>a</sub>(x<sup>*</sup>)
+
-
 
+
-
== Метод Ньютона: общий случай для m уравнений ==
+
-
{|
+
-
|rowspan= "4"|{
+
-
|f<sub>1</sub>(x<sub>1</sub>, x<sub>2</sub>, &hellip;, x<sub>m</sub>) = 0
+
-
|rowspan="4"| (6)
+
-
|-
+
-
|f<sub>2</sub>(x<sub>1</sub>, x<sub>2</sub>, &hellip;, x<sub>m</sub>) = 0
+
-
|-
+
-
|&hellip;
+
-
|-
+
-
|f<sub>m</sub>(x<sub>1</sub>, x<sub>2</sub>, &hellip;, x<sub>m</sub>) = 0
+
-
|-
+
-
|}
+
-
 
+
-
* (J(x))<sub>ij</sub> = (&delta;f<sub>i</sub>/&delta;x<sub>j</sub>), i, j = 1&hellip;m
+
-
* x<sup>n + 1</sup> = x<sup>n</sup> &minus; J<sup>&minus;1</sup>(x<sup>n</sup>)f(x<sup>n</sup>), n = 0, 1, &hellip;, x<sup>0</sup> &isin; U<sub>a</sub>(x<sup>*</sup>) (6)
+
-
* x<sup>n + 1</sup> = x<sup>n</sup> &minus; J(x<sup>0</sup>)f(x<sup>n</sup>)
+
-
 
+
-
== Метод секущей (хорд) ==
+
-
* x<sup>n + 1</sup> = x<sup>n</sup> &minus; f(x<sup>n</sup>)/f'(x<sup>0</sup>), n = 0, 1, &hellip;
+
-
* f'(x<sup>n</sup>) = (f(x<sup>n + 1</sup>) &minus; f(x<sup>n</sup>))/(x<sup>n + 1</sup> &minus; x<sup>n</sup>)
+
-
 
+
-
== Комбинированный метод ==
+
-
Подставим в метод Ньютона приближение производной:
+
-
* x<sup>n + 1</sup> = x<sup>n</sup> &minus; (x<sup>n</sup> &minus; x<sup>n &minus; 1</sup>)f(x<sup>n</sup>)/(f(x<sup>n</sup>) &minus; f(x<sup>n &minus; 1</sup>))
+
-
 
+
-
== Скорость сходимости метода Ньютона ==
+
-
* Z<sub>n</sub> = x<sup>n</sup> &minus; x<sub>*</sub> — погрешность
+
-
* &exist; M &gt; 0: 0,5|S'&#39;(x~<sub>n</sub>)| &le; M
+
-
* |Z<sub>n</sub>| &le; (M|Z<sub>0</sub>|)<sup>2<sup>n</sup></sup>/M = 1/M &times; q<sup>2<sup>n</sup></sup>
+
-
 
+
-
== Скорость сходимости модифицированного метода Ньютона ==
+
-
* S'(x) = 1 &minus; f'(x)/f'(x<sup>0</sup>)
+
-
* S'(x<sub>*</sub>) = 1 &minus; f'(x<sub>*</sub>)/f'(x<sub>0</sub>)
+
-
Чем ближе это значение к нулю, тем ближе скорость сходимости к методу Ньютона.
+
-
 
+
-
{{Курс Численные Методы}}
+

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


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

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

Получено с http://esyr.us/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B%2C_%D0%9E%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F
Личные инструменты
Разделы