2.2.1 Прямой метод решения слау

Будем решать систему (2.2.11) с помощью LU – разложения, где матрицы L и U имеют следующее строение:

_{Ниже приведен псевдокод алгоритма LU-разложения:}

_{for i=2 to m-1 do}

_{end do}

Получив LU – разложение, система (2.2.11) преобразуется к виду:

(2.2.1.1)

Псевдокод алгоритма решения системы (61):

_{for i=2 to m do}

end for

_{for i=m-1 to 1 do}

_{end for}

Рассмотрим пример численного решения уравнения Блека-Шоулза для европейского «Call» и «Put» опционов с параметрами E=10, r=0.1, , T=1. S изменяется в пределах от 0 до 50, t – от 0 до T. На рис.1 приведены графики решения (схема дискретизации Кранка-Никольсона на сетке n=m=250):

Рис. 1. Слева стоимость «Call» опциона, справа стоимость «Put» опциона

На рис.2 изображено поведение ошибки при решении различными методами на сетке n=m=250 для «Call» опциона (рис. 2а для схемы с опережением, рис. 2б для схемы Кранка-Никольсона, рис. 2в для схемы BDF2, рис. 2г. для схемы Рунге-Кутты).

а)

_{Рис. 2. Поведение ошибки приближенного решения для различных схем}

На рис.2 видны осцилляции ошибки, возникающие из-за негладкости в начальном условии. В таблице 1 приведены аналогичные результаты для различных m и n.

_{Таблица 1} Сравнение различных разностных схем по максимальной ошибке на сетке

m	n	максимальная ошибка на сетке
		схема с опережением	схема Кранка-Никольсона	BDF2 схема	двухшаговая схема Рунге-Кутты
8	8	0,13	0,15	0,14	0,15
16	16	0,31	0,30	0,30	0,30
32	32	0,060	0,050	0,054	0,050
64	64	0,013	0,014	0,012	0,014
128	128	0,0095	0,0047	0,0078	0,044
256	256	0,014	0,0076	0,022	0,0057
512	512	0,0092	0,006	0,0092	0,0021
1024	1024	0,0053	0,0051	0,0053	0,0021
2048	2048	0,0039	0,0048	0,0039	0,0017

_{Из таблицы 1 видно, что двухшаговая схема Рунге-Кутты обеспечивает наилучший результат при измельчении шагов.}

2.2.2 Итерационные методы решения слау

_{Рассмотрим итерационный метод решения СЛАУ (2.2.11) - метод последовательной верхней релаксации - Successive Over Relaxation (SOR). Метод SOR можно рассматривать как модификацию метода Гаусса-Зейделя, который в свою очередь можно рассматривать как модификацию метода Якоби.}

_{Рассмотрим метод Якоби – метод простой итерации для решения СЛАУ. Для того, чтобы построить итеративную процедуру метода, необходимо провести преобразование системы уравнений (2.2.11) к виду:}

_{где D - диагональная матрица, у которой на главной диагонали стоят соответствующие элементы матрицы A, а матрицы L и U содержат нижнюю и верхнюю треугольные части A, на главной диагонали которых стоят нули. Тогда процедура нахождения решения имеет вид:}

(2.2.2.1)

Теорема 1. [ссылка] Пусть ||B||<1. Тогда при любом выборе начального приближения :

1. Метод Якоби сходится.

2. Скорость сходимости равна скорости сходимости геометрической прогрессии со знаменателем q=||B||.

3. Верна оценка погрешности: , где .

Перейдем к рассмотрению метода Гаусса-Зейделя. Необходимое преобразование для построения итеративной процедуры:

Где L, D и U имеют те же значения, что и раньше. Тогда процедура нахождения имеет вид:

(2.2.2.2)

Основное отличие метода Гаусса-Зейделя от метода Якоби заключается в том, что новые значения в первом используются сразу же по мере получения, в то время как в методе Якоби они не используются до следующей итерации.

Теорема 2. [ссылка] Пусть ||C||<1, где . Тогда при любом выборе начального приближения :

1. Метод Гаусса-Зейделя сходится

2. Скорость сходимости метода равна скорости сходимости геометрической прогрессии со знаменателем q=||C||

3. Верна оценка погрешности: , где

Несмотря на то, что метод Гаусса-Зейделя – последовательный, он более предпочтителен, нежели метод Якоби. На практике он показывает более высокую скорость вычислений и стабильность.

Теперь перейдем к методу SOR. Здесь на каждом шаге итерации каждая компонента вектора решений представляет собой средневзвешенное между предыдущей итерацией по методу SOR и значением этой компоненты, полученным по методу Гаусса-Зейделя: где GZ – значение компоненты, вычисленное по методу Гаусса-Зейделя. В матричной форме процедура нахождения решения будет иметь вид:

(2.2.2.3)

где w – параметр релаксации. Заметим, что при w равным единице, SOR представляет собой метод Гаусса-Зейделя.

Теорема 3. [ссылка] Пусть ||C||<1, где и . Тогда при любом выборе начального приближения :

1. Метод последовательной релаксации сходится.

2. Скорость сходимости метода равна скорости сходимости геометрической прогрессии со знаменателем q=||C||.

3. Верна оценка погрешности: , где .