Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Подготовка к применению метода простой итерации






1. Подбор матрицы D в общем случае. Результаты предыдущего параграфа ставят проблему о нахождении для решения системы A·X = b методом простой итерации такой матрицы D, что ||B|| = ||In – D·A|| < 1. Такая матрица была указана в случае, когда матрица A с диагональным преобладанием.

В общем случае можно в качестве матрицы D брать вычисленную приближённо матрицу A–1. Более подробно: если предположить, что A = In + e·K, где 0 < e < 1 и компоненты kij матрицы K таковы, что |kij| < 1, то достаточно положить D = In – e·K + e2·K2 – … + (–1)s·es·Ks для некоторого s Î N. Действительно, матрица

B = In – D·A = In – (In – e·K + e2·K2 – …+ (–1)s·es·Ks)·(In + e·K) = (–1)s·es+1·Ks+1

при достаточно большом s имеет сколь угодно малую норму. Как правило, в большинстве случаев достаточно ограничиться первым приближением при s = 1.

Для приведения матрицы A к виду In + e·K можно воспользоваться методом Гаусса с выбором главных элементов, обнуляя только компоненты, не меньшие e. Для получения искомой матрицы потребуется гораздо меньше элементарных преобразований, чем для приведения её к диагональному виду.

Пример. Решить систему с точностью D = 0, 001.

В результате получена система с основной матрицей A = I4 + e·K, где e» 0, 8. Используя вспомогательный множитель D = I4 – e·K, получаем матрицу

B = I4 – (I4 – e·K)·(I4 + e·K) = (e·K)2 = .

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

2. Критерий сходимости метода простой итерации. Сформулируем без доказательства следующую теорему [1, стр. 270]:

Теорема (необходимое и достаточное условие сходимости метода простой итерации). Если B – невырожденная квадратная матрица, то метод простой итерации Xk+1 = B·Xk + e будет сходиться при любом начальном приближении X0 тогда и только тогда, когда модули всех собственных значений матрицы B меньше 1.

Таким образом, для обеспечения сходимости метода необходимо вести борьбу за уменьшение собственных чисел матрицы B = In – D·A, что не всегда эквивалентно малости нормы этой матрицы. Например, у матрицы B = собственное число l = 0, 5 < 1, но

||B||¥ = 100, 5 = ||B||1, ||B||2 = > 1.

Собственные числа матрицы B = In – D·A имеют вид 1 – m, где m – собственные числа матрицы D·A. Действительно, (In – D·A)· v = l· v Û Û D·A· v = (1 – l)· v, так что m = 1 – l, l = 1 – m. Поэтому нужно найти такую матрицу D, чтобы все собственные числа m матрицы D·A лежали (на комплексной плоскости) в круге радиуса 1 с центром в точке 1 Î R: |l| < 1 Û |1 – m| < 1.

3. Симметризация матрицы А. Если известно, что все собственные числа матрицы A вещественны и положительны, то в качестве матрицы D можно взять некоторый положительный скаляр. В самом деле, легко понять, что модули собственных чисел матрицы не превосходят любой её нормы: из v = x· v следует ||A· v || = ||x· v || = |x|·|| v ||, а значит, . Поэтому, положив D = , получим матрицу D·A, собственные числа которой вещественны, положительны и не превосходят ||D·A|| = .

Для обеспечения положительности собственных чисел матрицы A можно перейти от исходной системы A·X = b к равносильной её системе At·A·X = At·b, у которой основная матрица At·A имеет вещественные положительные собственные числа. Действительно, если At·A· v = x· v, то |A· v |2 = = (A· v)t·(A· v) = vt ·At·A· v = vt ·(x· v) = x·(vt · v) = x·| v |2, т.е. .

Описанный процесс перехода от системы линейных уравнений A·X = b к системе At·A·X = At·b называется симметризацией, т.к. получающаяся при этом матрица At·A будет симметричной: (At·A)t = At·(At)t = At·A.

Пример. Решить систему с точностью 0, 001.

Симметризуем систему:

Получена симметричная матрица At·A с нормой ||At·A||¥ = 11, 75 = ||At·A||1. Значит, согласно описанной теории,

.

В данном случае потребовалось всего восемь итераций, чтобы приблизиться к точному решению x = y = z = t = 1 с заданной степенью точности. Такая быстрая сходимость обусловлена тем, что ||B||¥ = ||B||1» 0, 995 < 1.

Ввиду того, что компоненты матрицы B и вектора e после симметризации могут быть малыми, величины Di могут не отражать истинную скорость сходимости итерационного процесса. Поэтому её следует оценивать по норме невязки xi = A·Xi – b исходной системы (см. последний столбец вышеприведённой таблицы).

Замечание: Нужно учитывать, что если матрица А имела малые собственные числа, то симметризация приводит к матрице с ещё меньшими собственными числами, т.е. к почти вырожденной матрице. Это может увеличивать погрешности вычислений и существенно замедлять сходимость метода простой итерации.

2. Для системы , решённой в начале параграфас точностью до 0, 001, вычисления с помощью симметризации сходятся крайне медленно.

Проведём симметризацию системы:

,

.

Получена симметричная матрица At·A с нормой ||At·A||¥ = ||At·A||1»» 9, 7758. Значит, как и ранее,

.

О сходимости итерационного процесса говорят следующие фрагменты вычислений:

Как видно, получаемые приближения очень далеки от найденного ранее приближённого решения x» 6, 146; y» –1, 523; z» –5, 646; t» –2, 353 даже при достаточно близком начальном приближении к нему. Поэтому для устранения подобных ситуаций разработаны различные методы ускорения сходимости итерационных процессов (см. например, [1], глава IV, §§ 4, 6, 8), о которых нет возможности более подробно говорить в этих лекциях.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.