Теормин по темам с пометками, где взять доказательства
Описание файла
Документ из архива "Теормин по темам с пометками, где взять доказательства", который расположен в категории "". Всё это находится в предмете "численные методы" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "Теормин по темам с пометками, где взять доказательства"
Текст из документа "Теормин по темам с пометками, где взять доказательства"
FAQ: Численные Методы, часть I
Системы линейных алгебраических уравнений: прямые методы
1. Связь метода Гаусса с разложением матрицы на множители.
См. [2], стр. 151; [3], стр. 43 (2.3); [6], стр. 17.
Рассмотрим простейший вариант метода Гаусса для решения СЛАУ вида Ax=b. Нетрудно показать, что в процессе прямого хода фактически происходит разложение матрицы А в произведение вида A=LU, где L - нижнетреугольная и U - верхнетреугольная матрицы. Такое разложение получило название LU-разложения.
Если найдено LU-разложение матрицы А, то дальнейшее решение системы Ax=b с произвольной правой частью b сводится к следующей схеме: 1) Ly=b, 2) Ux=y.
Теорема 1.1. Если все главные миноры матрицы А отличны от нуля, то ее LU-разложение единственно.
В современных программах, реализующих метод Гаусса, вычисления разбиваются на два основных этапа. Первый этап - это вычисление LU-разложения матрицы системы; на этом этапе производится основная масса вычислений - примерно (2/3)m3 операций. Второй этап - обработка правых частей и вычисление решений.
2. Обращение матрицы методом Гаусса-Жордана.
См. [6], стр. 30; [3], стр. 36 (2.1), [7], стр. 19.
Задача обращения матрицы. Будем искать для невырожденной матрицы А обратную A-1=V. Равенство AV=E равносильно совокупности равенств Av1=e1, Av2=e2 , ... , Avn=en , где vi и ei - столбцы матриц V и Е. Данная совокупность линейных уравнений с различными правыми частями решается произвольным методом.
Метод Гаусса-Жордана отличается от метода Гаусса в следующем. На i шаге прямого хода исключение переменной xi производится не только из уравнений i+1, i+2, ... , n, как в методе Гаусса, а из всех уравнений системы, кроме i-го. В результате прямого хода матрица системы приводится к единичному виду, и нет необходимости в обратном ходе.
3. Метод квадратного корня решения систем линейных уравнений.
Также известен как метод Холецкого;
См. [2], стр. 158; [3], стр. 96 (2.9), [6], стр. 34; [7], стр. 23.
Метод применяется для симметрических положительно определенных матриц A. Будем искать разложение вида A=LLT, где L - нижнетреугольная матрица.
Формулы для вычисления разложения Холецкого:
, (j = i+1,...,n) (3.1)
Вычисление производится последовательно для i=1,2,..,n. Если найдено разложение Холецкого матрицы А, то дальнейшее решение системы Ax=b с произвольной правой частью b сводится к следующей схеме: 1) Ly=b, 2) LTx=y.
Достоинства метода: асимптотическая скорость, экономия памяти, гарантированная устойчивость. Недостатки: неуниверсальность, необходимость в операции вычисления квадратного корня.
FAQ: Численные Методы, часть II
Системы линейных алгебраических уравнений: итерационные методы
4. Примеры и канонический вид итерационных методов решения СЛАУ.
См. [2], стр. 175.
Итерационный метод называется одношаговым, если на каждой итерации требуется результат лишь одной предыдущей итерации. Каноническая форма:
. (4.1)
На каждой итерации в общем случае решается уравнение относительно хn+1. Если B=E, метод назывется явным:
. (4.2)
Если B, - постоянные величины, метод называется стационарным.
Метод простой итерации. Для проведения итераций система приводится к виду x=Bx+c. Выбирается начальное приближение x0, а далее проводятся вычисления по следующей схеме: xn+1=Bxn+c.
Представим матрицу А в виде A=A1+D+A2, где D=diag[a11,....,amm] - диагональ матрицы А, A1 и A2 - соответственно нижнетреугольная и верхнетреугольная подматрицы.
Простейший вариант методо простой итерации - метод Якоби. В этом методе производится исключение переменной xi из i-го уравнения исходной системы. Метод Якоби имеет следующую каноническую форму:
D(xn+1 - xn) + Axn = f. (4.3)
Метод Зейделя можно рассматривать как модификацию метода Якоби. Основная идея модификации состоит в том, что при вычислении очередного (k+1)-ого приближения к i-ой переменной используют уже найденные (k+1)-ые приближения к переменным 1,...,i-1.
Каноническая форма метода Зейделя:
(D+A1)(xn+1 - xn) + Axn = f, (4.4)
Пусть B1 и B2 - соотвественно нижняя и верхняя треугольные части матрицы B. Тогда расчетные формулы метода Зейделя можно записать в следующем виде: xn+1=B1xn+1+B2xn +c.
Обобщением метода Зейделя является метод верхней релаксации:
, (4.5)
где - заданный числовой параметр. При =1 - это метод Зейделя.
5. Теорема о сходимости двухслойных итерационных методов.
Погрешность метода (4.2) на n-й итерации характеризуется вектором невязки zn=xn-x, который, очевидно, удовлетворяет однородному уравнению
. (5.1)
Теорема 5.1 (достаточное условие сходимости). Пусть А - симметрическая положительно определенная матрица и - положительно определенная матрица. Тогда при любом выборе начального приближения итерационная последовательность, определенная канонической формой (4.1), сходится к решению системы Ах=b.
6. Достаточные условия сходимости методов Якоби, Зейделя, релаксации.
См. [8, стр. 86].
Будем говорить, что А - матрица с диагональным преобладанием, если каждый диагональный элемент больше суммы абсолютных величин остальных элементов в соответствующей строке:
(6.1)
Применим теорему 5.1 к конкретным итерационным методам:
Утверждение 6.1. Пусть А - симметричная положительная матрица с диагональным преобладанием. Тогда метод Якоби (4.3) сходится.
Утверждение 6.2. Пусть А - симметричная положительная матрица. Тогда метод верхней релаксации (4.5) сходится при 0<<2. В часности, метод Зейделя (=1) сходится.
7. Теорема об оценке скорости сходимости итерационных методов и следствия из этой теоремы.
См. [8, стр. 95].
Если для погрешности итерационного метода верна оценка
||zn|| qn ||zo||, (7.1)
то говорят, что метод сходится со скоростью геометрической прогрессии со знаменателем q.
Будем рассматривать только стационарные итерационные методы вида
. (7.2)
Пусть для двух симметричных матриц А и В неравенство А В означает, что (Ax,x) (Bx,x) для любых векторов x. Для симметричной положительно определенной матрицы D введем обозначение .
Теорема 7.1. Пусть А и B - симметричные положительно определенные матрицы, для которых справедливы матричные неравенства
1B A 2B, (7.3)
где 2 > 1 > 0. При значении параметра
(7.4)
итерационный метод (7.2) сходится и для погрешности справедливы оценки
, (7.5)
, (7.6)
где
(7.7).
Утверждение 7.2 (следствие 1). Если А - симметричная положительно определенная матрица, а 1 и 2 - соотвественно минимальное и максимальное собственные значения этой матрицы, то для метода простой итерации
, (7.8)
в котором параметр выбирается по формуле (7.4), справедлива оценка
, (7.9)
где величина знаменателя определяется из (7.7).
Утверждение 7.3 (следствие 2). Для симметричной матрицы А, минимальное и максимальное собственные значения равны соответственно 1 и 2, и параметра , выбираемого по формуле (7.4), справедливо равенство
, (7.10)
где величина определяется формулой (7.7).
8. Попеременно-треугольный итерационный метод. Реализация метода. Теорема о сходимости.
См. [8, стр. 394].
Пусть дано матричное уравнение вида
Ax = f , (8.1)
с симметричной положительно определеной матрицей А порядка m. Построим верхнетреугольную матрицу R[rij] следующим образом:
. (8.2)
Очевидно, матрицу А можно представить в виде суммы A=R+R*.
Попеременно-треугольный итерационный метод относится к неявным стационарным методам вида (7.2), где матрица B имеет следующий конкретный вид (>0 - числовой параметр) :
B = (E+R*) (E+R). (8.3)
Вычисления по этому методу сводятся к решению на каждой итерации двух систем с треугольными матрицами.
9. Теорема об оценке скорости сходимости попеременно-треугольного итерационного метода.
См. [8, стр. 397]
Теорема 9.1. В обозначениях пункта 8, предположим, что существуют положительные постоянные и , при которых выполнены неравенства
A E, 4RR* A. (9.1)
Введем также обозначения
. (9.2)
Если параметры и попеременно-треугольного итерационного метода выбираются следующим образом:
, (9.3)
то этот метод сходится, причем для погрешности справедлива оценка
, (9.4)
где
. (9.5)
FAQ: Численные Методы, часть III
Проблема собственных значений
10. Степенной метод решения частичной проблемы собственных значений.
См. [6], стр. 82.
Степенной метод применяется для нахождения максимального по модулю собственного значения матрицы. k-ое приближение к этому значению вычислется так:
, (10.1)
Теорема 10.1. Пусть матрица A имеет полную систему из ортонормированных собственных векторов ei , которым соответсвуют собственные значения (i) , причем
|(1)| > |(2)| ... |(n)| (т.е. вектора занумерованы в порядке невозрастания модуля собственного значения, причем собственное значение (1) - не кратное).
Тогда итерационный процесс (10.1) сходится к собственному значению (1), причем
. (10.2).
При этом величины сходятся к собственному вектору e1 (c точностью до постоянного сомножителя, по модулю равного 1):
. (10.3)
11. Метод обратных итераций и обратных итераций со сдвигом решения частичной проблемы собственных значений.
Пусть найдено достаточно точное приближение ' к собственному значению . В методе обратных итераций приближения к собственному вектору e, соответсвующему , определяют последовательным решением систем уравнений
(A - 'E) yk+1 = xk (11.1)
с последующей нормировкой решения:
. (11.2)
В качестве начального приближения берут произвольный ненулевой вектор x0.
12. Приведение матрицы к верхней почти треугольной форме при помощи преобразования отражения.
См. [3, стр. 484 (11.5)], [6, стр. 70].