Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

gos / шпоры / ЧМ

.doc
Скачиваний:
13
Добавлен:
27.03.2016
Размер:
276.99 Кб
Скачать

1. Метод Гаусса решения систем линейных алгебраических уравнений. Выбор главного элемента.

Метод Гаусса.

Решаем СЛАУ:

Выполняем n-1 шаг вперёд (приведение матрицы к верхнеугольной), потом n-1 шаг назад (нахождение х)

По аналогичной формуле преобразуются все нижеследующие строчки.

На (n-2)-ом шаге получается треугольная матрица.

Метод Гаусса с выделением главного элемента.

1) В текущей строке находится

2) Переставляются столбцы (то есть переименовываются хi в хj и наооборот), чтобы оказался спереди.

Метод дает выше точность для матриц большой размерности

2. Метод простой итерации и метод Гаусса-Зейделя решения систем линейных алгебраических уравнений. Исследование сходимости.

Метод простой итерации решения СЛАУ.

Сходится, если хотя бы одна норма у B < 1 по модулю, т.е., например, если max|| < 1.

Этот метод имеет ограниченную область сходимости.

Доказательство:

Напишем это же самое в развёрнутом виде:

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

Усовершенствуем предыдущую систему:

Свойства:

  1. Скорость сходимости увеличивается.

  2. Можно останавливаться в середине итерации (в середине цикла).

  3. Области сходимости той же мощности (некоторые матрицы, которые методом последовательных приближений сходятся, методом Зейделя сходиться не будут, и наоборот).

  4. Нет требования к симметричности или положительности .

Метод обеспечения сходимости метода Зейделя.

то две СЛАУ равносильны

тогда

Выбор H, чтобы все || < 1 у HA

Итерационный процесс:

1)

2) Если 1) не дало результата (процесс не стал сходиться).

Ищем блоки 2*2, если их нечётное количество, то останется 1 блок 1*1=ann

3) и т. д.

3. Обращение матриц методом окаймления.

А:

На k-ом шаге находится обратная матрица углового минора kk, при этом известна обратная матрица для предыдущего углового минора (k-1)(k-1).

Будем искать Аk-1 в виде (матрица):

Pk-1 rk

qk 1/k

Аk*Ak-1 = E = [Ak-1 Uk; Vkk]*[ Pk-1 qk; rk 1/k] =

[Ak-1*Pk-1+Uk*qk Ak-1*rk+Uk*1/k; Vk*Pk-1+k*qk Vk*rk+k*1/k] =

= [Ek-1 0; 0 1]

(1) Ak-1*Pk-1+Uk*qk = E;

(2) Ak-1*rk+Uk*1/k = 0;

(3) Vk*Pk-1+k*qk = 0T;

(4) Vk*rk+k*1/k = 1;

Следовательно:

rk = -Аk-1-1 * Uk/k; (5)

Где Аk-1-1 известна на предыдущем шаге.

Подставим (5) в (4):

Vk*(-Аk-1-1*Uk/k) + k/k = 1;  k = k - Vkk-1-1*Uk;

Подставим в (5):

rk = -Аk-1-1 * Uk/k;

Выразим из (1) Pk-1­ и подставим в (3):

qk = -Vkk-1/k;

Pk-1­ = Аk-1-1 + (Аk-1*Uk*Vk Аk-1-1)/k.

4. Преобразование Хаусхолдера.

(Для приведения матрицы n*n к виду Хессенберга ровно за n-2 итерации)

Некоторые определения (воспоминания).

D – диагональная:

Q – ортогональная:

R – правая (верхняя) прямоугольная:

L – левая (нижняя) треугольная:

H – Хессенберга : 1) правая, верхняя

2) левая, нижняя

Подобные матрицы: если  Q, что B = QTAQ (у подобных матриц одинаковые собственные значения)

Конец воспоминаний

Выполняется n-2 шага (начиная с последней строки, и далее вверх).

На каждом шаге:

Исключаем нулевые элементы в очередной строке (j<i-1),

Пример i-ого шага: работаем со строкой l = n-i+1

До главн. диаг.

i =4

1) Рассчитывается величина

2)

3) ( это скаляр )

4) ( это матрица)

5) - (первую Р не транспонируем, т.к. матрица симметричная)

5. QR – разложение матрицы.

Задача представить матрицу А в виде произведения: , где Qортогональная ( -- верхнетреугольная.

Теорема: Если А – верхняя матрица Хессенберга, то у неё существует

QR – разложение, и оно осуществляется последовательным уничтожением поддиагональных нулей.

Уничтожаем а21 : (в общем случае: аij, где j = i+1)

Берём , где

Получаем:

Домножим слева на

Получим:

Алгоритм:

1) Находим

2)

n-1)

6. Нахождение собственных чисел при помощи QR-разложения. Основные свойства полученной последовательности подобных матриц.

Нахождение всех у матрицы при помощи QR – разложения.

Первоначально матрицы надо привести к виду Хессенберга. После этого можно запускать итерационный процесс.

-- раскладываем

-- перемножаем

-- раскладываем

-- перемножаем

Делаем, пока сумма квадратов элементов на диагонали не станет значительно больше суммы квадратов элементов под диагональю; либо пока матрица не перестаёт меняться (этот второй критерий используется, если есть комплексно-сопряжённые ).

Свойства метода.

Свойства итерационной последовательности (А(i)).

1) В пределе получается верхне-блочнотреугольная матрица, в которой на диагонали стоят  в порядке убывания, а блоки 2*2 соответствуют комплексно-сопряжённым .

2) Если исходная была симметричная матрица (при действительных ), то получится диагональная матрица, если не симметричная, то треугольная.

Скорость сходимости определяется тем, как стремятся к нулю недиагональные элементы:

Все поддиагональные элементы на каждом шаге уменьшаются, что приводит к уменьшению суммы квадратов элементов под диагональю.

7. Нахождение собственных чисел при помощи QR-разложения со сдвигом.

Нахождение всех у матрицы при помощи QR – разложения со сдвигом.

Это пример, когда обычный метод QR-разложения работает медленно.

Алгоритм разложения со сдвигом:

-- раскладываем

-- перемножаем

где -- некоторые числа.

Свойства метода, свойства полученной последовательности матриц

 1) тот же (В пределе получается верхне-блочнотреугольная матрица, в которой на диагонали стоят  в порядке убывания величины -l, а блоки 2*2 соответствуют комплексно-сопряжённым .)

2) скорость сходимости: a i j  0 так же, как  0

Если , то скорость -- быстрее, чем у обычного метода

Если то после (n-1) итерации все аij = 0.

8. Численное решение обыкновенных дифференциальных уравнений методом Рунге-Кутта 4-го порядка. Критерии точности и сходимости. Выбор оптимальной величины шага интегрирования.

Метод Рунге-Кутта 4-ого порядка. Общая часть: Поставка задачи.

1) Задача Коши

2) Система ДУ

3) Уравнение с высшими производными

тоже Задача Коши, как 1) и 2)

1), 2), 3) – одно и тоже (один вид постановки задачи может быть преобразован к другому)

Пример этого преобразования:

Для системы 5-ого порядка:

Алгоритм Рунге-Кутта:

Тогда,

Для системы: всё точно также, только стоят вектора над k, f, y.

Распишем вектора в нормальном виде.

При описании k надо не забыть, что это 2-мерная матрица 4*n:

Критерий устойчивости:

Критерий точности:

(Для многомерного случая вместо берется у матрицы частных производных )

Критерий увеличения (уменьшения) шага:

(при динамическом определении шага)

если crit > порог 1, то надо уменьшить шаг, если Crit < порог 2 < порог 1, то можно шаг увеличить.

Алгоритм:

  1. Считаем у матрицы частных производных в

  2. Берём

  3. Делаем 1-ый шаг и считаем

  4. Устанавливаем пороги:

9. Численное решение обыкновенных дифференциальных уравнений методом прогноза и коррекции. Области применимости метода.

Метод прогноза и коррекции 4-ого порядка.

Таких методов много, отличаются значением коэффициентов коррекции.

Алгоритм:

  1. Считаем методом RK4 (первые 3 шага)

Дальше собственно метод:

Делаем расчёты, исходя из прогноза, для которого нужна основа, например, 4 точки (поскольку метод 4-ого порядка) в качестве начальных условий.

  1. Расчёт предсказания:

  2. Изменение предсказания:

  3. Изменение производной:

  4. Коррекция:

  5. Значение в точке xi+1:

Гарантированная погрешность.

Свойства:

  1. 2 раза расчёт f на каждом шаге (остальные f рассчитаны ранее)

  2. Погрешность < a = o(h5)=

Достоинства метода: 1) маленькая погрешность

2) всего 2 раза высчитываем функцию.

Недостатки метода: не может работать самостоятельно, сначала надо прорешать несколько шагов методом RK.

10. Метод прогонки для решения систем линейных алгебраических уравнений с трехдиагональной матрицей.

Решение трёх-диагональных СЛАУ методом прогонки.

Решение (алгоритм):

Ищем решение в виде: , где и неизвестные пока функции.

Подставим в исходную систему:

1, 1 берутся из 1-ого начального условия:

Алгоритм.

  1. Находим 1, 1 из 1-ого начального условия.

  2. Прямая прогонка: i = 1, 2, …, n-1

cчитаем все i+1 и i+1

  1. Из последнего начального условия находим xn

  2. Обратная прогонка: i = n, n-1, …, 1

18

Соседние файлы в папке шпоры