Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Метод обобщенных минимальных невязок





Пусть пространства K и L связаны соотношением L=AK, причем в качестве K используется подпространство Крылова Km(n1,A) с выбором n1=r0/b, b=||r0||2. Для построения ортонормированного базиса воспользуемся ортогонализацией Арнольди. Вместо проектирования (2.16) рассмотрим эквивалентную задачу минимизации функционала f(x)=||rx||22 на пространстве K. Так как любой вектор x из пространства (x0+Km) может быть записан в виде

x=x0+Vmy,

где y вектор размера m. Таким образом, задачу минимизации функционала можно переписать как

ym=argminy||b–A(x0+Vmy)||22.

Вычислительная схема, построенная с использованием таких предпосылок, называется методом обобщенных минимальных невязок (GMRES).

С использованием определения вектора n1 и соотношений (2.30), (2.32) имеем

r=b–A(x0+Vmy)=Vm+1(be1 y).

Поскольку матрица Vm+1 составлена из ортонормированных столбцов, справедливо равенство

y(y)=f(x0+Vmy)=||be1 y||22. (2.47)

Таким образом, для нахождения коэффициентов линейного комбинирования векторов {ni} в GMRES необходимо решить СЛАУ

. (2.48)

которая является переопределенной (так как матрица имеет размерность (m+1)´m).

Матрица системы (2.48) имеет верхнюю хессенбергову форму. Поэтому (2.48) проще всего решать с помощью предварительного приведения к верхнетреугольному виду; последняя строка при этом обнуляется. С учетом хессенберговой формы наиболее простым вариантом оказываются вращения Гивенса. Всего необходимо m таких вращений G1, G2,…,Gm, причем Gk строится так, чтобы его применение к (hkk,hk+1,k)T обнуляло второй компонент этого вектора.

Структура матриц G1 и G2 имеет вид

Числа s и c связаны соотношением s2+c2=1 (это позволяет их интерпретировать как синус и косинус некоторого угла) и определяются как:

Очевидно, что при программной реализации нет необходимости в непосредственном хранении матриц вращения Gi, так как каждая такая матрица полностью определяется двумя числами – косинусом и синусом угла поворота – и индексами компонент вектора, к которым применяется вращение.

Основной проблемой в GMRES является выбор размерности m пространства K; хранение базисных векторов этого пространства определяет основные затраты памяти при программной реализации метода, составляющие mN чисел. Наиболее распространенной модификацией GMRES является перезапускаемый GMRES или GMRES(m). Выбирается некоторая размерность m<N, определяемая, по существу, лишь доступным объемом памяти, и после обновления решения x=x0+Vmym оно принимается за новое начальное приближение, после чего процесс повторяется.



Далее приведен алгоритм предобусловленного метода GMRES(m) с вращениями Гивенса.

Алгоритм метода GMRES(m) с вращениями Гивенса

Если необходимо построить матрицу предобусловливателя M
Выбрать m < N и произвольное начальное приближение x(0)
z = b – A x(0)
g=||z||2
Найти r(0) из системы M r(0) =z
b = ||r(0)||2
Создать ((m + 1) ´ m) - матрицу H
Создать вектор (m + 1) - вектор q
ДляNit =1, 2, … до сходимости или до Nitmax
H = 0; q= b e1
n1= r(0)/b
Дляi=1,…,m
z=An(i)
Найти w из системы Mw=z
Для k=1,…,i
hki=(w, n(k))
w=w–hkin(k)
увеличить k
hi+1,i=||w||2
n(i+1)=w/hi+1,i
Дляk=1,…,i–1
(h1i,…, hi+1,i)T=Gk(h1i,…, hi+1,i)T
увеличить k
Построить Gi так, что [Gih×,i]i+1=0
q=Giq
увеличить i
Решить треугольную СЛАУ H1:p,1:py=q1:p
z=b–Ax(0)
Найти r0 из системы Mr0=z
b=||r(0)||2
Продолжать пока b/g³ tol

Алгоритм начинается с того, что требуется задать произвольное начальное условие x(0) (третий параметр метода). Итерационный процесс продолжается до тех пор, пока не будет получено решение, с точностью определяемое параметром tol (четвертый параметр)или при достижении максимального числа итераций Nitmax (пятый параметр). Также необходимо, чтобы пользователь определил размерности m (шестой параметр).В случае необходимости использовать метод без предобусловливани необходимо инициализировать седьмой параметр нулем. В противном случае необходимо задать:

- 10 в случае использования метода с предобусловливанием, основанном на LU-разложении с выбором структуры разреженности, основанном на норме строки;

- 11 в случае использования метода с предобусловливанием, основанном на LU-разложении с выбором структуры разреженности, основанном на норме столбца;

- 12 в случае использования метода с предобусловливанием, основанном на LU-разложении с выбором структуры разреженности, основанном на норме матрицы;

-20 в случае использования метода с предобусловливанием, основанном на ILU(0) разложении с выбором структуры разреженности, основанном на норме строки;

- 21 в случае использования метода с предобусловливанием, основанном на ILU(0) разложении с выбором структуры разреженности, основанном на норме столбца;

-22 в случае использования метода с предобусловливанием, основанном на ILU(0) разложении с выбором структуры разреженности, основанном на норме матрицы.

Также для использования метода с предобусловливанием необходимо задать точность обнуления (t) определяемую восьмым параметром.

Пример использования метода GMRES(m) с вращениями Гивенса в системе TALGAT:

- действительный случай: SET "solve" GMRES_r real_m right_r 0. 1.e-8 150 15 10 1.e-4;

- комплексный случай: SET "solve" GMRES complex_m right_c 0. 1.e-8 150 15 10 1.e-4.





Дата добавления: 2014-12-27; Просмотров: 1284; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:

  1. A. Матеріали методичного забезпечення для основного етапу заняття
  2. BTL–ATL методи міжнародної маркетингової комунікації: сутність, особливості та сфери застосування.
  3. Compare Means - простые параметрические методы сравнения средних.
  4. I. МЕТОДИКА ИССЛЕДОВАНИЙ В СОЦИАЛЬНОЙ РАБОТЕ
  5. I. Методические рекомендации (материалы) для преподавателя
  6. I. Методы организации и осуществления учебно-познавательной деятельности
  7. I.2. Философский уровень методологического анализа педагогических конфликтов
  8. I.3. Общенаучный уровень методологического анализа педагогических конфликтов
  9. I.4. Конкретно-научный уровень методологического анализа педагогических конфликтов
  10. I.5. Методико-технологический уровень анализа педагогических конфликтов
  11. II) Вероятностные методы расчета надежности систем.
  12. II. Методические основы определения рыночной стоимости интеллектуальной собственности.

studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.003 сек.