авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 | 3 |
-- [ Страница 1 ] --

СТАВРОПОЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Кириллова Людмила Николаевна

Развитие и

модификация метода Зейделя приближенного

решения операторных уравнений

05.13.18 – Математическое моделирование, численные методы

и комплексы программ

Диссертация

на соискание ученой степени

кандидата физико-математических наук

Научный руководитель:

доктор физико-математических наук, профессор, член-корреспондент АН Таджикистана В.Я. Стеценко Ставрополь – 2005 ОГЛАВЛЕНИЕ ВВЕДЕНИЕ…………………………………………………………………... 5 ГЛАВА 1. Метод Зейделя и его развитие………………………………….. §1. Сравнительный анализ метода Зейделя с методом последовательных приближений………………………………………………………….. 1.1. Метод Зейделя для решения систем линейных алгебраических уравнений……………………………………………………………… 1.2. Норма оператора как одна из возможных характеристик скорости сходимости метода последовательных приближений…... 1.3. Точные значения и оценки матричных норм…………………... 1.4. Спектральный радиус и его оценки…………………………….. 1.5. О возможности эквивалентной перенормировке пространства, при которой норма неотрицательной матрицы будет сколь угодно близкой к значению ее спектрального радиуса…………………….. 1.6. Операторная форма записи метода Зейделя. Обобщение метода Зейделя………………………………………………………... §2. Достаточное условие, гарантирующее более высокую скорость сходимости метода Зейделя по сравнению с методом последовательных приближений…………………………………….. §3. Ускорение сходимости метода Зейделя решения систем линейных алгебраических уравнений…………………………………………… §4. Некоторые варианты модификации метода Зейделя………………….. 4.1. Связь скорости сходимости метода Зейделя с его порядком….. 4.2. Синтез метода Зейделя с методом однопараметрического итеративного агрегирования………………………………………….

ГЛАВА 2. Развитие метода Зейделя на случай интегральных уравнений и операторных уравнений произвольной природы.…………………... §1. Метода Зейделя для приближенного решения интегральных уравнений……………………………………………………………… 1.1. Распространение метода Зейделя на класс интегральных уравнений……………………………………………………………… 1.2. Вспомогательные факты теории конусов………………………. 1.3. Сравнение спектральных радиусов r(A) и r(D) интегральных операторов А и D = ( I A1 ) 1 A2, где A = A1 + A2 …………………….

1.4. Ускорение сходимости метода Зейделя …………………….





.…. §2. Метод Зейделя для уравнений с абстрактным оператором в банаховом пространстве с телесным и нормальным конусом……... 2.1. Полуупорядоченное пространство……………………………… 2.2. Реализация метода Зейделя в случае абстрактного оператора………………………………………………………………. 2.3. Достаточное условие более быстрой сходимости метода Зейделя по сравнению с методом последовательных приближений…………………………………………………………... 2.4. Ускорение сходимости метода Зейделя………………………… §3. Развитие метода Зейделя на случай пространств с нетелесным конусом……………………………………………………………….... ГЛАВА 3. Оценки спектрального радиуса линейного оператора………….... §1. Двусторонние оценки спектрального радиуса линейных операторов…. 1.1. Оценки спектрального радиуса интегрального оператора……… 1.2. Оценки спектрального радиуса абстрактного оператора………... 1.3.Уточнение оценок спектрального радиуса……………….…………... §2. Новые оценки сверху спектрального радиуса интегрального оператора……………………………………………………………… §3. Двусторонние оценки решения операторного уравнения…………….. §4. Алгоритм определения скорости сходимости метода Зейделя для уравнений в гильбертовом пространстве…………………………… §5. Метод построения приближений по недостатку и по избытку к x, положительному собственному вектору отвечающему ведущему собственному значению…………………………………… 5.1. Случай линейного положительного оператора………………… 5.2. Случай нелинейного оператора…………………………………. ЗАКЛЮЧЕНИЕ………………………………………………………………. ЛИТЕРАТУРА………………………………………………………………... ПРИЛОЖЕНИЯ………………………………………………………………. ВВЕДЕНИЕ Многие математические модели экономических, физических, инженерных задач могут быть реализованы с помощью операторных уравнений. К операторным уравнениям приводится также широкий класс задач анализа, алгебры, теории интегральных и дифференциальных уравнений. При этом в большинстве случаев соответствующие уравнения приходится рассматривать в полуупорядоченных пространствах. Это объясняется тем, что, как правило, в постановке задачи практического содержания существенную роль играют соображения, связанные с положительностью решения или монотонной зависимостью решения от некоторых входящих в уравнение элементов.

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

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

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

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





Исследованию этих вопросов и посвящена данная диссертация, которая продолжает исследования в области теории операторных уравнений и применение к их приближенному решению численных методов, проведенные М.Г. Крейном, О.И. Прозоровской, М.А. Красносельским, В.Я. Стеценко и их учениками.

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

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

Для достижения поставленной цели необходимо решить следующие задачи.

1. Провести сравнительный анализ скорости сходимости метода Зейделя и метода последовательных приближений (МПП) к точному решению линейных систем алгебраических уравнений, интегральных уравнений, уравнений с абстрактным оператором, действующим в банаховом пространстве с телесным и нормальным конусом, интегральных уравнений в пространстве функций с нетелесным конусом, с целью указания наиболее рационального метода.

2. Разработать варианты модификации метода Зейделя по ускорению сходимости к точному решению различных классов операторных уравнений.

3. Уточнить двусторонние оценки значений спектрального радиуса линейного оператора.

4. Применить разработанные методы к нахождениям приближенных решений операторных уравнений.

5. Создать программное обеспечение, позволяющее реализовать предложенные методы.

выполненной диссертации заключается в Научная новизна следующем:

1. При сравнении метода Зейделя с МПП, получены достаточные условия, гарантирующие более высокую скорость сходимости метода Зейделя. Приведены формулы, характеризующие величину зазора между приближениями, полученными по методу Зейделя и по МПП при решении различных классов операторных уравнений.

2. Разработаны приемы ускорения сходимости метода Зейделя.

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

4. Выведен алгоритм определения скорости сходимости метода Зейделя для уравнений в гильбертовом пространстве.

5. Предложен метод построения приближений по недостатку и по x, отвечающему избытку к положительному собственному вектору ведущему собственному значению.

6. Разработаны программы на языке программирования TURBO PASCAL, позволяющие реализовывать некоторые из полученных в данной работе методов и алгоритмов.

Методы исследований. Решение поставленных научных задач основывается на использовании численных методов, математического моделирования, функционального анализа, теории положительных операторов, действующих в полуупорядоченных пространствах.

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

Эффективность предложенных методов подтверждается результатами вычислительных экспериментов.

Практическая ценность Практическая значимость работы.

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

На защиту выносятся следующие положения:

1. Достаточные условия, обеспечивающие более высокую сходимость метода Зейделя по сравнению с МПП для различных классов операторных уравнений.

2. Варианты модификации метода Зейделя по ускорению сходимости к точному решению различных классов операторных уравнений.

3. Уточненные оценки спектрального радиуса линейного оператора.

4. Метод построения приближений по недостатку и по избытку к точному решению линейных и нелинейных операторов.

Реализация результатов. Теоретические и практические результаты работы использованы в учебном процессе СГУ в рамках дисциплин специализации.

Результаты работы докладывались на Апробация работы.

международной школе-семинаре по геометрии и анализу памяти Н.В.Ефимова (Абрау-Дюрсо, 2002г.), на зимней математической школе «Современные методы теории функций и смежные проблемы» (Воронеж, 2003г.). На 49-й, 50-й научно-методических конференциях преподавателей и студентов «Университетская наука - региону» (Ставрополь, 2004г., 2005г.).

На IV,V-й региональных научно-практических конференциях «Совершенствование методов управления социально-экономическими процессами и их правовое регулирование» (Ставрополь, 2004г., 2005г.), на XXXIV научно-технической конф. по результатам работы профес.-препод.

состава, аспирантов и студентов Сев.-Кав. ГТУ за 2004 г. (Ставрополь, г.) Перейдем к краткому изложению содержания диссертации.

Глава 1 диссертации посвящена методу Зейделя и его развитию. В § проводится сравнительный анализ скорости сходимости двух численных методов: метода последовательных приближений и метода Зейделя [4] к решению систем линейных алгебраических уравнений вида n xi = aij x j + bi (i = 1, n) (1) j = На основе проведенного анализа обосновываются достаточные условия, при которых метод Зейделя обеспечивает более быструю сходимость к решению линейных систем алгебраических уравнений в сравнении с методом последовательных приближений.

Для исследования этого и подобных вопросов, применяемых не только к методу решения систем линейных алгебраических уравнений, но и к решению более общих классов операторных уравнений, приведены некоторые известные факты теории операторных уравнений.

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

Приведем известную [33] теорему, позволяющую оценить скорость сходимости метода последовательных приближений с помощью нормы оператора.

Теорема 1.1. Пусть Е – линейное нормированное пространство, А – линейный оператор, действующий в Е, и А - норма этого оператора в банаховом пространстве Е, порожденная какой-либо нормой х Ев пространстве Е. Тогда для любого, удовлетворяющего неравенству A, уравнение x = Ax + f при каждом f E имеет, и притом единственное, решение x = x( f ) и к этому решению сходится последовательность {xm }:

xm +1 = Axm + f (m = 0,1,...) (2) x0 E, при этом выполняется при любом начальном приближении неравенство m A x ( f ) x m +1 x1 x0, которое является оценкой близости приближения xm +1 к точному решению x ( f ).

Формула (2) определяет метод последовательных приближений.

Утверждение теоремы 1.1, при всем его значении, не может полностью снять вопрос о скорости сходимости метода (2), так как норма оператора вводится по заданной в пространстве E норме элементов. В этой связи в рассмотрение вводится числовая характеристика, являющаяся инвариантом в классе всех эквивалентных норм пространства Е.

Определение 1.1. Спектральным радиусом r(А) линейного оператора А, действующего в банаховом пространстве Е, называется величина r ( A) = lim n An, n если этот предел существует.

Роль спектрального радиуса линейного положительного оператора поясняется следующей теоремой [31].

Теорема 1.6. Если r ( A), то уравнение вида x = Ax + f при любом f из банахова пространства E имеет и притом единственное решение, которое может быть получено по методу последовательных приближений xn +1 = Axn + f (n = 0,1,2,...) при любом начальном приближении x0 из E.

Из приведенного результата следует, что метод последовательных r ( A) приближений сходится тем быстрее, чем меньше величина.

Применим метод Зейделя к исходной системе (1). Для этого запишем ее в операторной форме:

x = Ax + f, (3) где A = (aij ), x R n, f Rn.

Положим A = A1 + A2, где 0 0 a11 a12... a1n 0...

a 0... 0 0 a22... a2 n A1 = 21 A2 =,. (4).........

...............

a 0 0... ann n1 an 2... Выбрав каким-либо образом, начальное приближение x0 R n образуем последовательность приближений xm +1 = A1 xm +1 + A2 xm + f (m = 0,1,...), (5) которая является фактически операторной формой записи метода Зейделя.

Пусть I- единичная квадратная матрица, тогда метод (5) можно записать в виде ( I A1 ) 1 xm +1 = A2 xm + f. (6) Предполагая, что матрица ( I A1 ) 1, обратная матрице ( I A1 ), существует, формулу (6) перепишем в виде xm +1 = ( I A1 ) 1 A2 xm + ( I A1 ) 1 f, т.е. метод Зейделя запишется в виде метода последовательных приближений xm +1 = Dxm + f1, (7) где D = ( I A1 ) 1 A2, f1 = ( I A1 ) 1. Это значит, что при соответствующей нормировке пространства R n скорость сходимости метода Зейделя совпадает со скоростью сходимости метода последовательных приближений (7), которая сколь угодно близка к скорости сходимости геометрической прогрессии со знаменателем близким к значению спектрального радиуса r (D) матрицы D.

Таким образом, в случае, когда r ( D ) r ( A), (8) метод (7) сходится быстрее метода последовательных приближений. При выполнении равенства r ( A) = r ( D) скорости сходимости двух методов одинаковы.

Достаточные условия того, что метод Зейделя сходится не медленнее метода последовательных приближений, приведены в следующей теореме.

Теорема 1.11. Пусть A1, A2 0 и выполняется условие r ( A1 ) 1. Тогда выполняется неравенство r ( D) r ( A), т.е. метод Зейделя определен и сходится не медленнее, чем метод последовательных приближений для решения уравнения x = Ax + f.

В §2 указаны условия, гарантирующие выполнение в (8) строгого неравенства, т.е. более высокую сходимость метода Зейделя по сравнению с методом последовательных приближений.

Теорема 1.12. Пусть матрица А1 переводит каждый вектор u0 с положительными координатами в вектор A1u0 с положительными координатами, т.е. из u0 0 следует, что A1u0 0.

Тогда имеет место строгое неравенство r ( D ) r ( A).

Следствием теоремы 1.12 является неравенство r ( A) r ( D) (9).

Справедливость последнего неравенства проверяется непосредственно.

Неравенство (9) позволяет оценить «зазор» между r ( A) и r (D) и, тем самым, позволяет выяснить, эффективность применения метода Зейделя в сравнении с методом последовательных приближений. Этот «зазор» не меньше, чем правая часть неравенства (9).

Теорема 1.12 допускает развитие на случай, когда у матрицы А1 не обязательно все элементы строго больше нуля, но, как и прежде предлагается, что A 0 и r ( A) 1.

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

Определение 1.2. Выпуклое множество K E называется конусом, если вместе с каждой своей точкой x оно содержит луч, проходящий через x, и если из x, x K вытекает, что x = 0 (лучом, проходящим через точку x E x 0, называется совокупность точек tx (t 0) ).

Определение 1.3. Оператор А называется u0 -ограниченным снизу, где u0 0 - фиксированный ненулевой элемент конуса K, если для каждого x можно указать такое натуральное m=m(x) и такое = ( x) 0, для которых выполняется неравенство Am x u0, и называется u0 -ограниченным сверху, если для каждого х 0 существует такое натуральное n = n(x) и такое = ( x) 0, что An x u0.

Теорема 1.13. Пусть матрица А1 является u0 -ограниченным сверху + + оператором относительно конуса Rn и для элемента u 0 Rn при некотором 1 0 выполняется неравенство A1u 0 1 u 0. Тогда r ( D) r ( A).

§3 посвящен ускорению сходимости метода Зейделя решения систем линейных алгебраических уравнений вида (3). Для решения таких уравнений по методу Зейделя строятся приближения vn и wn по недостатку и по избытку соответственно, которые являются монотонными и сходятся к единственному решению х*, при этом для каждого n выполняется неравенство v n x wn.

{vn } {wn } сходятся к х* В ряде случаев последовательности и недостаточно быстро. В связи с этим указан прием, позволяющий построить новые двусторонние приближения, сходящиеся к х*, вообще говоря, быстрее, {vn } {wn }.

чем и Эти методы иллюстрируются соответствующими примерами. Рассмотренный прием реализован при помощи программы на языке программирования TURBO PASCAL, разработанной автором совместно с Плютой А.И. (приложение 1).

В §4 рассматривается модификация метода Зейделя, позволяющая ускорить процесс нахождения приближенного решения систем алгебраических уравнений.

Теоретические результаты и вычислительные эксперименты свидетельствуют об увеличении скорости сходимости метода Зейделя с возрастанием «порядка» этого метода. В связи с этим введем понятие «порядка» метода Зейделя: если присоединить к матрице А1 (4) главную диагональ, то в этом случае метод Зейделя примет вид неявной схемы, при которой для определения (m+1)-го приближения по компоненте с номером i, необходимо решить для каждого i одно скалярное уравнение с неизвестным yi( m+1). Этот метод называем методом Зейделя первого порядка.

Соответственно, если в А1 включить еще одну выше расположенную диагональ, параллельную главной, то для определения yi( m+1) придется решать систему двух уравнений с двумя неизвестными yi( m+1) и yi(+1+1).

m Соответствующий метод называем методом Зейделя второго порядка. По аналоги вводятся методы Зейделя третьего и более высокого порядков.

Несмотря на то, что с «ростом» матрицы A1, реализация метода Зейделя усложняется, эксперименты подтверждают, что чем выше порядок метода Зейделя, тем выше скорость сходимости приближений к точному решению.

При этом необходимо учитывать величину «зазора» между r (D) и r ( A) : при незначительном отклонении r (D ) от r ( A) увеличивать порядок метода Зейделя становиться нецелесообразно.

В этом же параграфе предлагается еще один вариант метода Зейделя, представляющий собой синтез метода Зейделя и метода однопараметрического итеративного агрегирования. Вычислительные эксперименты свидетельствуют о том, что у предложенного синтеза метода Зейделя различных порядков и метода однопараметрического итеративного агрегирования заметно выше скорость сходимости приближений к точному решению, по сравнению с другими итерационными методами (метод последовательных приближений, метод Зейделя в классической интерпретации и др.) при относительно больших значениях r ( A).

По этому методу разработана автором программа на языке программирования TURBO PASCAL (приложение 2).

Развитию метода Зейделя на случай интегральных и операторных уравнений произвольной природы посвящена глава 2 диссертации.

В §1 этой главы исследуется применение метода Зейделя в пространстве С[ a, b ] для решения интегральных уравнений вида b x(t ) = K (t, s ) x( s )ds + b(t ) (10) a с непрерывным по совокупности переменных t и s, неотрицательным ядром K (t, s ). Для этого класса уравнений применим как метод последовательных приближений b xm +1 (t ) = K (t, s ) xm ( s )ds + b(t ) (m = 0,1,...), a так и метод Зейделя, который в данном случае может быть представлен в форме b b уm +1 (t ) = K1 (t, s ) ym +1 ( s )ds + K 2 (t, s ) ym ( s )ds + b(t ) (m = 0,1,...), (11) a a где K1 (t, s ) и K 2 (t, s ) таковы, что K (t, s) = K1 (t, s ) + K 2 (t, s), (12) K1 (t, s ) 0, K 2 (t, s ) 0.

Тем самым, метод (11) можно трактовать как достаточно полный аналог метода Зейделя решения линейных систем алгебраических уравнений.

При этом в представлении (12) в качестве ядра K1 (t, s) удобно брать вырожденное ядро, так как при построении приближений по методу Зейделя (11) необходимо на каждом (m+1)-ом шаге решать интегральное уравнение (11) относительно неизвестной функции ym+1 ( s ), что достаточно просто реализовывать в случае интегрального уравнения с вырожденным ядром. Это связано с тем, что решение интегральных уравнений с вырожденным ядром можно свести [54] к решению линейной системы алгебраических уравнений.

Представим уравнение (10) в виде x = Ax + b. (13) А = А1 + А2, где Пусть Ai - интегральный оператор с ядром Ki 0 (i = 1,2), тогда уравнение (13) примет вид ( I A1 ) x = A2 x + b. (14) Предположим, что существует оператор ( I A1 ) 1, обратный оператору ( I A1 ), причем обратный оператор ( I A1 ) 1 действует в том же пространстве C[a,b ]. Тогда уравнение (14) разрешимо относительно x = x(t ) и его решение может быть представлено в виде x = ( I A1 ) 1 A2 x + ( I A1 ) 1 b, или x = Dx + ( I A1 ) 1 b, где D = ( I A1 ) 1 A2. (15) Как и в случае решения линейных систем алгебраических уравнений, основой для сравнения этих двух методов служит спектральный радиус интегрального оператора. Здесь рассматривается пространство C[ a,b ], полуупорядоченное относительно конуса K непрерывных, неотрицательных на [a, b] функций. Отметим, что в случае, если r ( A) 1, то существует оператор ( I A) 1. Для любого неотрицательного непрерывного ядра K1 (t, s ) такого, что 0 K1 (t, s ) K (t, s ) (16) выполняется неравенство: r ( A1 ) r ( A), где А1 - оператор с ядром K1 (t, s ) [21].

Поэтому также существует оператор ( I A1 ) 1, причем этот оператор является положительным, т.е. для x K также ( I A1 ) 1 x K.

Теорема 2.1. Пусть для ядер K1 (t, s ) и K (t, s) интегральных операторов A1 и A выполняется условие (16), а также условие: r(A)1, тогда метод Зейделя ym +1 = Dym + ( I A1 ) 1 b (m = 0,1,...), где D – оператор вида (15), сходится, и имеет место неравенство r ( D) r ( A).

Естественно, что в этом случае, как и для случая линейных алгебраических систем, возникает вопрос о том, когда будет иметь место строгое неравенство r ( D) r ( A). (17) Ответ на этот вопрос дает следующая теорема.

Теорема 2.2. Пусть интегральный оператор b A1 x(t ) = K1 (t, s ) x( s )ds a переводит каждую положительную функцию u0 (t ) в положительную функцию A1u0 (t ). Тогда справедливо неравенство (17) для спектральных радиусов интегральных операторов D и A.

Замечание. Полученное при доказательстве теоремы неравенство r ( A) r ( A)(1 ) r ( D) = r ( A) (18) 1 позволяет оценить эффект ускорения сходимости метода Зейделя по сравнению с методом последовательных приближений. Этот эффект определяется величиной «зазора» между величинами r(D) и r(A). Согласно оценке (18) он не меньше, чем r ( A) r ( A), 1 и тем больше, чем больше. Величина 0 определяется в соответствии с неравенством A1u0 (t ) u0 (t ).

Отсюда следует «качественный» вывод: чем большая часть А1 оператора А включена в обращаемую часть выражения ( I A1 ) 1, т.е. в оператор D, тем заметнее будет эффект ускорения сходимости метода Зейделя в сравнении с методом последовательных приближений.

Предложенный в §3 главы 1 метод ускорения сходимости двусторонних приближений к неизвестному решению x, полученных по методу Зейделя, в случае систем линейных алгебраических уравнений допускает дальнейшее развитие на случай решения линейных интегральных уравнений и систем таких уравнений. В пункте 1.4 §1 главы 2 указаны приемы ускорения сходимости метода Зейделя.

В §2 исследуется применение метода Зейделя для уравнений с абстрактным оператором, действующим в банаховом пространстве с телесным и нормальным конусом.

Рассматриваются операторные уравнения вида x = Ax + b, (19) где x- неизвестный элемент банахова пространства Е, А – линейный оператор произвольной природы, действующий в пространстве Е, b – произвольный элемент этого пространства. При этом предполагается, что в Е выделено множество K «неотрицательных» элементов, называемое конусом и обладающее свойствами, которые называются аксиомами конуса [32].

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

Пусть Е - банахово пространство с телесным и нормальным конусом K.

Конус K называется нормальным, если существует такая постоянная С, что из неравенства y x y следует, что x C y.

Рассмотрим уравнение x = ( A1 + A2 ) x + b с оператором A = A1 + A2, у которого A1, A2 0, r ( A) 1. Для решения уравнения (19) применим метод Зейделя ym +1 = A1 ym +1 + A2 ym + b (m = 0,1,...), где y0 - начальное приближение, выбранное произвольно.

Определение 2.1 [56]. Оператор А будем называть неразложимым в пространстве Е, если из неравенств x0 Ax0, x0 0, x0 0, где 0 следует, что x0 внутренний элемент конуса K.

Теорема 2.5. Пусть оператор А1 переводит множество K внутренних элементов K в себя:

A1 K K, конус K нормален и телесен.

Тогда r ( D) r ( A).

Более того, если для u0 K выполняется неравенство A1u0 u0, где 0, то r ( A) r ( D) r ( A). (20) Неравенство (20), наряду с информацией качественного характера о более быстрой сходимости метода Зейделя, позволяет провести количественные исследования о том, насколько метод Зейделя сходится быстрее, чем метод последовательных приближений. Эффект ускорения при этом, очевидно, не меньше, чем величина r ( A) r ( A) r ( D) r ( A).

1 В том случае, когда скорость сходимости окажется не достаточно высокой в пункте 2.4 исследуется возможность ускорения сходимости метода Зейделя.

В §3 предлагается развитие метода Зейделя на случай пространств с нетелесным конусом. В таких пространствах важную роль играют уравнения с u0 -ограниченным снизу (соответственно, u0 -ограниченным сверху) оператором.

Оператор А называется u0-положительным, если для каждого x 0 и для некоторых p = p ( x), = ( x) 0, = ( x) 0, выполняется неравенство 1u0 A p x 1u0.

Каждый u 0 -ограниченный снизу и u0 -ограниченный сверху оператор А является u 0 -положительным оператором [59].

x0 K E Определение 2.2. Будем говорить, что является квазивнутренним элементом конуса, если для каждого ненулевого функционала l K выполняется неравенство l ( x0 ) 0.

Следующая теорема является развитием теоремы 2.5 на пространства с нетелесным конусом.

Теорема 2.6. Пусть операторы А и А1 являются u0 -положительными вполне непрерывными операторами относительно нормального и воспроизводящего конуса K, пусть r ( A) 1.

Тогда r ( D) r ( A).

Оценка величины зазора между r (D ) и r ( A) приведена в следующей теореме.

Теорема 2.8. Пусть операторы А и А1 являются u0 -положительными и для некоторого 0 выполняется условие A1u0 u0.

Тогда r ( A) r ( D).

Обоснование многих приближенных методов решения линейных операторных уравнений (в том числе метода Зейделя), а также различные теоретические вопросы требуют эффективных оценок спектрального радиуса линейных операторов.

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

Урысону, О. Перрону, М.Г. Крейну, М.А. Красносельскому и В.Я. Стеценко, состоит в том, что для достаточно широкого класса линейных положительных операторов оценку спектрального радиуса можно получить, исходя из характеристик поведения оператора на одном фиксированном элементе конуса K.

В главе 1 §1 приводились теоремы, позволяющие оценить спектральный радиус матрицы А, исходя из поведения этой матрицы на одном фиксированном ненулевом неотрицательном векторе из R n. В § главы 3 оценки спектрального радиуса матрицы распространены на более общий случай, в том числе, на случай интегральных операторов вида Ax(t ) = K (t, s )x( s )ds (21) с непрерывным или, в более общем случае, измеримым квадратично суммируемым неотрицательным ядром K (t, s ). Здесь - ограниченное n замкнутое множество в R2, а интеграл понимается в смысле Лебега.

Обозначим через r ( A) спектральный радиус интегрального оператора А с ядром K (t, s ), относительно которого предполагается выполненным условие ma1 (t )b1 ( s ) K (t, s ) Ma1 (t )b1 ( s ), a1 (t ), b1 ( s ) L2 (), a1 (t ), b1 ( s) 0 (t, s ), m где причем и M положительные постоянные. В этих условиях оператор (21), действующий в пространстве L 2 ( ), оставляет инвариантным конус K неотрицательных функций этого пространства и является и1-ограниченным сверху оператором, где u1 = a1 (t ).

Пусть для некоторой функции и 0 ( t ) 0, и 0 ( t ) 0, и 0 ( t ) L 2 ( ), и 0 ( t ) a 1 (t), где 0, выполняется неравенство Au0 (t ) 0u0 (t ) и v0 (t ) = 0u0 (t ) Au0 (t ).

Тогда на основании результатов работы [33] вытекает, что имеет место неравенство r ( A) 0.

Исследования в этом направлении привели к получению оценок сверху и снизу для величины [0 r ( A)], которые, в свою очередь, с одной стороны привели к двусторонним оценкам для r ( A), а с другой стороны позволили уточнить ранее известные оценки для r ( A). Получены следующие результаты.

Лемма 3.1. Пусть выполнено условие 0 = b1 ( s)a1 ( s)ds 0.

Тогда r ( A) m 0, в частности, r ( A) 0.

Определение 3.1. Оператор А называется фокусирующим на конусе K, x 0, y 0 существует если он u0 -положительный и если для всех постоянная 2 такая, что ( Ax, Ay ) 2.

При этом число называется постоянной фокусирования. (По поводу определения функционала см. [38]).

Пусть u0 0 фиксированный элемент конуса K, фиксированное число, 1. Через K u 0, будем обозначать множество всех x K, для которых существует a = a ( x) 0 такая, что a ( x)u0 x a ( x)u0.

Очевидно, что K u 0, удовлетворяет всем аксиомам конуса, при этом Ku0, K.

Приведем критерий фокусирования [61].

Утверждение 3.1. Для того, чтобы положительный оператор А был фокусирующим, необходимо и достаточно, чтобы существовали такие u0 K и const, что для каждого x K выполнялось бы неравенство ( x)u0 Ax ( x)u0, здесь u0 фиксированный элемент конуса K, ( x) 0.

Это утверждение означает, что AK K u 0,.

Следующая лемма показывает, что сопряженный с А оператор A является фокусирующим оператором и, более того, переводит конус K в конус K u 0,.

Лемма 3.2. Пусть функция а1(s) почти при всех s принимает положительные значения. Тогда A K К u 0,, M где u0=b1(t), а =.

m В перечисленных выше условиях справедлива теорема.

Теорема 3.1. Справедлива двусторонняя оценка для спектрального радиуса r(А) оператора A:

b1(t ) 0 (t )dt b1(t ) 0 (t )dt 0 r ( A) 0, b1(t ) u 0 (t )dt b1(t ) u 0 (t )dt где функция v0 = v0 (t ) определена формулой v0 (t ) = u0 (t ) Au0 (t ).

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

Теорема 3.2. Пусть l0 K - собственный вектор A, отвечающий собственному значению = r ( A) :

Al0 = r ( A)l0.

Положим v0 = 0u0 Au0 0.

Тогда справедлива двусторонняя оценка для спектрального радиуса r(А) (v ) 1 (v ) 0 l 0 0 r ( A) 0 l 0 0.

l 0 (u0 ) l 0 (u0 ) Пункт 1.3 посвящен уточнению оценок спектрального радиуса.

Теорема 3.3. Пусть А - линейный вполне непрерывный положительный на воспроизводящем конусе K оператор, обладающий свойством: r ( A) 0, и для каждого элемента l1 K существует = (l1 ) 0 такое, что l0 Al1 l0, где l0 - фиксированный ненулевой элемент из K, а 0 постоянная.

Пусть для некоторого квазивнутреннего элемента x0 K выполняется неравенство w0 = Ax0 0 x0 0.

Тогда справедлива двусторонняя оценка для r(A) 1 l0 ( w0 ) l (w ) 0 + r ( A) 0 + 0 0.

l0 ( x0 ) l0 ( x0 ) В §2 получены новые оценки сверху спектрального радиуса интегрального оператора вида Ax(t ) = K (t, s ) x( s )ds.

Рассмотрим функции P(t ) = K (t, s ) ds, Q(t ) = K ( s, t ) ds.

Теорема 3.4. Пусть для некоторого [0;

1] выполняется следующее неравенство P (t )Q1 (t ) 1 (t ) (22) и, кроме того, выполняется одно из двух условий:

10) в неравенстве (22) равенство допускается лишь на множестве точек лебеговой меры нуль;

20) в неравенстве (22) строгое неравенство выполняется для всех t из w, mes w 0, некоторого множества оператор А неразложим в пространстве L p ().

Тогда спектральный радиус r ( A) оператора А в пространстве L p () меньше, чем единица:

r ( A) 1.

В §3 полученные ранее результаты применены к нахождению оценок решения операторного уравнения с линейным положительным и неразложимым оператором А, действующим в пространстве Е с телесным и нормальным конусом K.

Рассмотрим уравнение x = Ax + f. (23) Теорема 3.5. Пусть u0 - внутренний элемент конуса K, а 0 таково, что 0u0 Au0 0.

Тогда r ( A) 0 и уравнение (23) имеет, и притом единственное, решение x = x ( f ) для каждого : 0 при любом fЕ. Это решение представимо рядом Неймана Am x =, m + m= причем при 0 для решения x справедлива априорная оценка fu fu (u0 v0 ) x (u0 v0 ).

0 (24) ( 0 ) ( 0 ) Эта оценка сравнивалась с ранее известной [61] априорной оценкой решения уравнения (23) f f u0 u u0 x u0. (25) 0 Оценка (24) всегда лучше оценки (25).

Полученные оценки развиты на случай, когда вместо условия 0u0 Au (соответственно вместо условия Ax0 0 x0 ) выполняются условия 0u0 Amu0.

Справедлива теорема.

Теорема 3.6. Пусть А - линейный вполне непрерывный положительный на воспроизводящем конусе K оператор, обладающий свойством: r ( A) 0, и для каждого элемента l1 K существует = (l1 ) 0 такое, что l0 Aml1 l0, где l0 - фиксированный ненулевой элемент из K, а 0 постоянная.

Тогда 1 l 0 ( 0) m 1 ( )m r ( A) 0 l 0 0, l 0 (u 0) l 0 (u 0 ) где v0 = 0u0 Amu0.

В §4 предложен алгоритм определения скорости сходимости метода Зейделя для уравнений в гильбертовом пространстве. В работе С.Г. Крейна и О.И. Прозоровской [40] был предложен метод решения уравнения вида Bx = b, (26) где В – самосопряженный оператор, действующий в гильбертовом пространстве Н. Если при принятых соответствующих условиях окажется, что спектральный радиус r(C) оператора C = ( B1 + B2 ) 1 B * меньше, чем 1, то к уравнению (26) применим метод последовательных приближений, быстрота сходимости которого определяется величиной r(C).

Работа [38] М.А. Красносельского, В.Я. Стеценко продолжает исследование статьи [40]. Здесь установлено, что для таких уравнений метод Зейделя, является сходящимся. Скорость сходимости метода определяется величиной спектрального радиуса оператора С, для которого установлена более точная оценка r (С ) 1, (27) B1 + B {((B + B )x, x) (B x, x )}.

где 0 определяется соотношением 0 = sup 1 2 x Так как 0 определено неявно, мы поставили задачу установить фактическое значение величины r (C ) или, по крайней мере, ее фактическую оценку сверху по определенным характеристикам тех операторов, которые входят в выражение оператора С.

Если в неравенстве (27) постоянную 0 заменить положительным числом 0, полученным по формуле 0 = ( B1 + B2 ) x0, x0 ) ( B2 x0, x0 ), где x0 * произвольный элемент конуса, нормированный условием ( x0, x0 ) = 1, то это позволяет оценить сверху «отрыв» числа r (C ) от числа r (C ) 1.

B1 + B В §5 излагается метод построения приближений по недостатку и по x, отвечающему избытку к положительному собственному вектору ведущему собственному значению.

В пункте 5.1. рассмотрен случай линейного положительного оператора.

При решении задачи на отыскание собственных значений уравнения x = Ax алгоритм построения приближений un и vn, определяется следующей теоремой Теорема 3.10. Пусть А – фокусирующий оператор с постоянной.

Тогда А имеет в K u o собственный вектор x, которому отвечает собственное значение 1 = r ( A). К этому вектору x сходится метод Axn x n +1 = (n = 0,1,2,...) Axn u o при любом x0 K u o, x0 0. При этом справедлива оценка близости qn ( x, xn ) ( х1, х0 ), 1 q 1. К собственному вектору x где q удовлетворяет неравенству q + также сходятся последовательности un и vn, причем u n x vn, где n n 1 1 1 a 2 +1 b 2 + An x0, An x0.

un = vn = b a Оператор A является оператором сжатия [35], а постоянные a и b таковы, что ax0 Ax0 bx0.

Если вместо оператора А взять сопряженный оператор A то, учитывая, что он является положительным в E относительно полугруппы K, мы аналогичным образом получаем способ построения приближений l1( n ), l2n ) к ( собственному функционалу оператора A : l1( n ) l0 l2n ).

( Здесь же предлагаются алгоритмы построения собственных векторов x и l операторов A и A, соответствующих значению 1 = r ( A).

По предложенным алгоритмам составлены программы на языке программирования TURBO PASCAL (приложение 3).

В процессе исследований оказалось, что приближения, сходящиеся к вектору x, можно построить для некоторых классов нелинейных операторов F(x). Этот случай рассматривается в пункте 5.2. Здесь выделен соответствующий класс нелинейных операторов F(x), действующих в полуупорядоченном банаховом пространстве, являющихся монотонными относительно нормального конуса K и такими, что F (x) F ( x) для всех x K и [1;

+], где 1, const.

Определение 3.2. Будем говорить, что x и y принадлежат одной составляющей конуса K, если существуют такие конечные числа и, что x y, y x, а сами элементы x и y в этом случае будем называть связными.

Составляющую конуса K, содержащую элемент u0, будем обозначать C K (u0 ).

Теорема 3.11. Пусть конус K нормален и пусть для некоторого u0 элементы u 0 и F (u0 ) принадлежат одной составляющей конуса K. Тогда для всех, 0 оператор F (x) имеет на составляющей C K (u0 ) собственный вектор x ( ), отвечающий собственному значению. Этот вектор может быть построен методом последовательных приближений x m +1 ( ) = F ( xm ( )) при любом начальном приближении x0 Cк (u0 ). При этом справедлива оценка близости m d ( x ( ), xm +1 ( )) d ( x1 ( ), x0 ( )). (28) Неравенство (28) позволяет также получить оценку относительной погрешности для приближений xm+1 ( ), т.е. оценку величины x ( ) x m +1 ( ).

x ( ) ГЛАВА МЕТОД ЗЕЙДЕЛЯ И ЕГО РАЗВИТИЕ §1. Сравнительный анализ метода Зейделя с методом последовательных приближений Значительное число задач анализа, алгебры, теории интегральных уравнений можно представить с единых позиций в виде линейного или нелинейного операторного уравнения вида x = A( x) + f (1.1) с оператором A(x), действующим в том или ином (вполне определенном) банаховом пространстве E. При этом для таких уравнений возникают весьма специфические задачи. Одной из них является довольно распространенная задача о существовании у уравнения (1.1), решения x = x, обладающего свойством неотрицательности. Такого рода задачи, вообще говоря, характерны в задачах экономики, для которых экономический смысл имеют, лишь неотрицательные решения (типичный пример – модель Леонтьева межотраслевого баланса). Подобные ситуации возникают также при решении физических и инженерных задач, например, задача о потоке нейтронов в ядерном реакторе.

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

Итерационные методы состоят в том, что решение x уравнения (1.1) (n ) находится как предел при n последовательных приближений x, где n номер итерации. Обычно задается некоторое число 0 (точность) и вычисления проводятся до тех пор, пока не будет выполнена оценка x ( n) x.

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

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

В дальнейшем нам понадобятся понятия норм вектора и матрицы.

Напомним определения основных норм в пространствах векторов и матриц [4]. Если в пространстве векторов x = ( x1, x2,..., xn )T введена норма x, то согласованной с ней нормой в пространстве матриц А называют норму sup Ax x A=.

x Наиболее употребительны в пространстве векторов следующие нормы:

n n = ( x, x ) 2, x 1 = xj, x 2 = xj = max x j, x 1 j n j =1 j = а согласованными с ними нормами в пространстве матриц являются соответственно нормы n ( ) n A = max aij A 1 = max aij, A 2 = maxi ( A A),.

1 i n j =1 1 j n i = Здесь i (D) - собственные значения матрицы D = A A, а A - матрица, сопряженная к матрице А (т.е. это результат комплексного сопряжения к матрице транспонированной по отношению к матрице А). Если матрица А – симметричная, то для нее A 2 = (max i ( A ) ), A 1 =.

min i ( A ) Метод последовательных приближений состоит в следующем.

Рассмотрим систему линейных уравнений x = Ax+ b. (1.2) Здесь A – квадратная неособенная матрица с элементами aij (i, j = 1,2,...n), b вектор столбец с элементами bi (i = 1,2,...n).

Выбрав начальное приближение x ( 0) = ( x1 0), x20),..., xn0) )T, подставим его ( ( ( в правую часть системы (1.2) и, вычисляя полученное выражение, находим первое приближение x (1) = Ax ( 0) + b.

Подставляя приближение x (1) в правую часть системы (1.2), получим x ( 2) = Ax (1) + b.

Продолжая этот процесс далее, получим последовательность x ( 0), x (1),..., x ( k ),... (1.3) приближений (векторов), вычисляемых по формуле x ( k +1) = Ax ( k ) + b, k = 0,1,2,... (1.4) Если последовательность (1.3) имеет предел x = lim x (k ), k то этот предел является решением системы (1.2). В самом деле, переходя к пределу при k в равенстве (1.4), будем иметь lim x ( k +1) = A lim x ( k ) + b k k или x = Ax + b, т.е. предельный вектор x является решением системы (1.2) а, следовательно, и системы (1.1).

Условие сходимости метода последовательных приближений дает следующая теорема.

Теорема 1.1 [4]. Итерационный процесс (1.4) сходится при любом векторе x (0) тогда и только тогда, когда i ( A) 1, где i ( A) все собственные значения матрицы A.

Для практики важна следующая теорема.

Теорема 1.2 [4] (о достаточном условии сходимости метода последовательных приближений). Если A 1, то процесс итераций (1.4) сходится к единственному решению x при любом начальном векторе x ( 0).

Чаще всего останавливаются на проверке двух условий:

1) A 1, 2) A 1 1.

Следствие. Для системы (1.1) метод последовательных приближений сходится, если матрица А имеет диагональное преобладание, т.е.

n aij aij.

i, j = i j Если x - вектор решения, а xk 1 и xk - два последовательных приближения решения линейной системы (1.2), то для оценки погрешности x xk применяют неравенство A x xk xk xk 1. (1.5) 1 A Эта оценка широко используется на практике. Если A, то формула (1.5) примет вид x x ( k ) x ( k ) x ( k 1), т.е. в этом случае, если x ( k ) x ( k 1), то и x x (k ).

В общем случае, если в процессе вычислений будет обнаружено, что 1 A x ( k ) x ( k 1) = 1, A где A 1, то x x ( k ) 1.

Последнее неравенство является критерием окончания итерационного процесса.

Метод Зейделя представляет собой некоторую модификацию метода последовательных приближений. Основная его идея заключается в том, что при вычислении (k + 1) -го приближения неизвестной xi( k + 1 учитываются уже вычисленные ранее приближения неизвестных x1 k + 1 ), x2 k + 1 ),..., xi( 1+ 1 ).

( ( k Пусть система (1.1) приведена к виду (1.2) или к виду n xi = Aij x j (i = 1,2,..., n).

j = Выберем произвольно начальные приближения неизвестных x1 0), x20),..., xn0).

( ( ( Далее предполагая, что k е приближения xi(k ) неизвестных xi известны, согласно Зейделю, будем строить (k + 1) - е приближение по следующим формулам:

x1 k +1) = A11 x1k + A12 x2 +... + A1n xn + b1, ( k k x2k +1) = A21 x1 k +1) + A22 x2 +... + A2 n xn + b2, ( ( k k...

xi( k +1) = Ai1 x1 k +1) + Ai 2 x2k +1) +... + Ain xn + bi ( ( k...

xnk +1) = An1 x1 k +1) + An 2 x2k +1) +... + Ann xn + bn, ( ( ( k (k = 0,1,2,...).

Заметим, что указанная теорема 1.2 о достаточном условии сходимости простой итерации остается верной для итераций по методу Зейделя.

Теорема 1.3 [4]. Пусть A 1, где A - одна из норм A, A 1. Тогда при любом выборе начального приближения x (0) метод Зейделя сходится со скоростью геометрической прогрессии, знаменатель которой q A.

Теорема 1.4 [4]. Пусть выполнено условие A1 + A2 1, где A1 + A2 = A. Тогда при любом выборе начального приближения x ( 0) метод Зейделя сходится.

Если для одной и той же системы метод последовательных приближений и метод Зейделя сходятся, то метод Зейделя предпочтительнее.

Однако области сходимости этих двух методов, вообще говоря, различны.

Приведем оценку погрешности приближений процесса Зейделя по норме. Если x - вектор решения, а x k 1 и x k - два последовательных приближения решения линейной системы (1.2), то для оценки погрешности x x (k ) применяют неравенство A x x ( k ) x ( k ) x ( k 1), 1 A1 где A1 + A2 = A и 0 0 a11 a12 a1n 0......

a21 0... 0 0 a22... a2 n A1 = a31 a32 0, A2 = 0 a3n.

... 0...

..................

......

a 0 ann n1 an 2... 0 0...

Полученное равенство позволяет сформулировать простой критерий окончания итерационного процесса. Если требуется найти решение с точностью 0, то итерации метода Зейделя следует вести до выполнения неравенства A x ( k ) x ( k 1) 1 A1 или эквивалентного ему неравенства x ( k ) x ( k 1) 1, где 1 A 1 =.

A 1.1. Метод Зейделя решения систем линейных алгебраических уравнений.

Рассмотрим систему:

n xi = aij x j + bi (i = 1, n). (1.6) j = По выбранному тем или иным образом начальному приближению ( ), x0 = x1 0), x20),..., xn0) строится последовательность приближений ( ( ( ( ) xm = x1 m ), x2m ),..., xnm ) ( ( ( (m = 1,2,...) к точному решению уравнения (1.6) при условии, что оно существует. Для метода последовательных приближений построение этой последовательности осуществляется по формулам = a11 x1 m 1) +... + a1n xnm 1) + b1, x1 m ) ( ( ( (m) = a21 x1 m 1) +... + a2 n xnm 1) + b2, ( ( x (1.7) (m) = a31 x1 m 1) +... + a3n xnm 1) + b3, ( ( x...

xnm ) = an1 x1 m 1) + an 2 x1 0) +... + ann xnm 1) + bn.

( ( ( ( В классическом методе Зейделя построение приближений проводится по формулам (m) n = aij y (jm 1) + b1, y j = n y (m) aij y (jm 1) + b2, = a21 y1 m ) + ( 2 j = n (1.8) y (m) + aij y (jm 1) + b3, a31 y1 m ) ( a32 y2m ) ( = + 3 j =...

(m) n = anj y (jm ) + ann y (jm 1) + bn.

yn j = xm = (x1( m ).x2m ),..., xnm ) ) и вместо векторов ( ( рассматриваются векторы ( ) ym = y1 m ), y2 m ),... yn m ) ( ( ( ( m = 1,2,...).

Тем самым в методе Зейделя при нахождении очередного приближения yk c номером k (k=1,2,…) для i-ой (i=1,2,…,n) координаты решения используются значения всех ранее найденных приближений с тем же номером k для предыдущих координат. Естественно предположить, что в случае сходимости метода каждое следующее приближение, должно быть ближе к решению по сравнению с предыдущим, и поэтому можно ожидать, что метод Зейделя обеспечивает более быструю сходимость, чем метод последовательных приближений. Тем не менее, известно [70], что метод Зейделя далеко не всегда способен «ускорить» процесс сходимости, иногда он приводит к обратному эффекту («замедлению» сходимости).

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

Для решения вопросов, связанных со скоростью сходимости метода последовательных приближений нам понадобятся некоторые известные факты теории операторных уравнений.

1.2. Норма оператора как одна из возможных характеристик скорости сходимости метода последовательных приближений.

Пусть в пространстве Е наряду с заданной в Е нормой x норма x 1, рассматривается еще какая-либо эквивалентная заданной.

Напомним, что две нормы x и x 1 называются эквивалентными, если можно указать такие положительные постоянные m и M, что для каждого x E выполняется неравенство mx x1M x.

Известно, что в любом конечномерном пространстве любые две нормы являются эквивалентными. В пространстве бесконечного числа измерений не всякие две нормы будут эквивалентными. Так, если в пространстве непрерывных функций х(t), заданных на отрезке [0,1], рассматривать две нормы:

x(t ) 1 = max x(t ) (1.9) 0 t и x(t ) 2 = x( s ) ds, (1.10) то эти две нормы не являются эквивалентными, ибо в противном случае из полноты пространства C[0;

1] по одной из норм вытекала бы полнота этого пространства по любой другой эквивалентной норме. В тоже время пространство C[0;

1] является полным по норме (1.9) и не является, как известно [48], полным по норме (1.10).

Приведем известную [33] теорему, позволяющую оценить скорость сходимости метода последовательных приближений с помощью нормы оператора.

Теорема 1.5. Пусть Е - линейное нормированное пространство, А линейный оператор действующий в Е, и A -норма этого оператора в x Eв банаховом пространстве Е, порожденная какой-либо нормой пространстве Е. Тогда для любого, удовлетворяющего неравенству A, (1.11) уравнение x = Ax + f (1.12) при каждом f E имеет, и притом единственное, решение x = x( f ), к которому сходится последовательность {xm } :

xm+1 = Axm + f (m=0,1,…) (1.13) x0 E. При этом справедливо при любом начальном приближении неравенство m A x ( f ) xm+1 x1 x0, (1.14) которое является оценкой близости приближения xm+1 к точному решению x ( f ).

Тем самым, метод последовательных приближений (1.13) при x ( f ) выполнении неравенства (1.11) сходится к точному решению A уравнения (1.12) со скоростью, не меньшей q =, т.е. не медленнее, чем геометрическая прогрессия qm :

m A qm =.

Доказательство этого утверждения является прямым следствием неравенства (1.14), которое, в свою очередь, является непосредственным следствием принципа Банаха сжатых отображений, так как формулу (1.13) можно переписать в том же виде, что и в классическом методе A последовательных приближений для уравнения с оператором. При этом при выполнении неравенства (1.11) A q1 A оператор является оператором сжатия. Свойство (1.11), влекущее за собой выполнение неравенства (1.14), позволяет получать дополнительные сведения о методе последовательных приближений. В частности, можно указать необходимый минимум шагов итерации m, который дает приближение к решению уравнения (1.12) с точностью, не превосходящей заданного числа 0.

1.3. Точные значения и оценки матричных норм.

Приведем некоторые наиболее часто используемые нормы матричных операторов.

n Рассмотрим в пространстве R матрицу a11 a12... a1n... a2 n a a A = 21 (1.15)......

......

a... ann n1 an 2 с вещественными или комплексными элементами aij.

= max x j, ( x = ( x1, x2,..., xn )).

1) Пусть x Тогда соответствующая j =1,n норма матрицы А вида (1.15) вычисляется по формуле n A = max aij i =1,n j = n 2) Пусть x 1 = x j. Тогда соответствующая норма A 1 матрицы А j = вычисляется по формуле n A 1 = max aij.

j =1,n j = n xi 3) Пусть x 2 =, т.е. в R n введена евклидова норма. Тогда j = соответствующая норма A 2 матрицы А допускает следующую оценку сверху:

n A2 aij. (1.16) i, j = Выражение (1.16) не позволяет получить точные значения нормы матрицы в случае евклидовой нормировки пространства. Можно доказать, что точное значение нормы матрицы А выражается формулой A = 1, где наибольшая абсолютная величина собственных значений симметричной матрицы AA, где A - сопряженная к А матрица, т.е. если A = (a ji ), где горизонтальная черта означает операцию A = (aij ), то комплексного сопряжения.

1.4. Спектральный радиус и его оценки.

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

Определение 1.1. Спектральным радиусом r(А) линейного оператора А, действующим в банаховом пространстве Е, называется величина r ( A) = lim n An, (1.17) n если этот предел существует.

Лемма 1.1 [31]. Величина предела (1.17) одна и та же в любой эквивалентной норме пространства Е.

Роль спектрального радиуса линейного положительного оператора поясняется следующей теоремой [31].

Теорема 1.6. Если r ( A), то уравнение вида x = Ax + f при любом f из банахова пространства E имеет и притом единственное решение, которое может быть получено по методу последовательных приближений xn +1 = Axn + f (n = 0,1,2,...) при любом начальном приближении x0 из E.

Из приведенного результата следует, что метод последовательных r ( A) приближений сходится тем быстрее, чем меньше величина.

Вычислить точное значение спектрального радиуса r ( A) оператора не всегда просто. В связи с этим большое значение приобретают его всевозможные оценки.

Для получения оценок спектрального радиуса матрицы удобно использовать следующий факт [59]: спектральным радиусом r ( A) неотрицательной матрицы А является наибольшая абсолютная величина собственных значений этой матрицы.

Теорема 1.7 (об оценке сверху спектрального радиуса неотрицательной матрицы) [59]. Пусть матрица А неотрицательная и для некоторого вектора u0 R n, с положительными координатами выполняется условие Au0 u0 ( 0).

Тогда r ( A).

Если же A m u 0 u для некоторого натурального m, то r ( A) m.

Теорема 1.8 (об оценке снизу спектрального радиуса неотрицательной матрицы) [59]. Пусть А- неотрицательная квадратная матрица и для некоторого вектора x0 R n, x0 0, x0 R+ выполняется неравенство n A m x 0 0 x 0.

Тогда r ( A) m 0.

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

n A = (aik ) Квадратная матрица называется Определение 1.2.

разложимой, если при некотором разбиении всех индексов 1,2,…,n на две дополнительные системы (без общих индексов) i1, i2,..., i ;

k1, k 2,..., kv ( + v = n) ( = 1,2,..., ;

= 1,2,..., v).

ai k = В противном случае матрица А называется неразложимой.

Теорема 1.9 (о строгой оценке спектрального радиуса неотрицательной матрицы) [59]. Пусть матрица А - неотрицательная и неразложимая и для некоторого вектора u 0 0, u 0 0 выполняется условие Au0 u0 ( 0), причем Au 0 u 0.

Тогда r ( A).

Если же A m u 0 u 0 ( A m u 0 u 0 ) для некоторого натурального m, то r ( A) m.

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

Между значениями спектрального радиуса r(A) и нормой A неотрицательной матрицы А при любом способе нормировки пространства R n существует следующая зависимость:

A r ( A). (1.18) Доказательство очевидно: пусть x0 0 - собственный вектор матрицы А, отвечающий r(А) (существование такого вектора гарантировано теоремой Перрона-Фробениуса [14]):

Ax0 = r ( A) x0.

Тогда A x0 Ax0 = r ( A) x0 = r ( A) x0, откуда, т.к. x0 0, имеем неравенство (1.18).

Тем самым, при любом способе нормировки пространства R n норма матрицы всегда не меньше, чем значение спектрального радиуса r(A).

В этой связи, представляет интерес, следующий результат:

Теорема 1.10 [59]. Для любого 0 можно всегда указать такую эквивалентную нормировку x пространства R n, для которой выполняется неравенство A r ( A) +, т.е. соответствующая норме x норма матрицы A отличается от r(А) не более чем на.

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

Доказательство. По определению r ( A) = lim n A n. (1.19) n Выберем 0 и положим r ( A) + = r. Согласно (1.19) существует такой номер n0 = n( ), для которого при всех n n An r. (1.20) n Введем по найденному n0 новую норму x 1 согласно формуле An1 x x Ax x1= + 2 +... +. (1.21) rn r r При этом новая норма удовлетворяет неравенству:

x1 x, (1.22) r с другой стороны An x A x1 1 + +... + n1 = M1 x, (1.23) r r r где An A M1 = 1 + +... + n1, r r r т.е. M 1 const. Из неравенств (1.22) и (1.23) следует, что обе нормы x и x 1, эквивалентны.

Для любого элемента х на основании (1.21) имеем An0 1 x An0 x A2 x Ax Ax 1 = + 2 +... + n0 1 + n0. (1.24) r r r r В силу (1.20) An0 x rn0 x. (1.25) На основании соотношений (1.24), (1.25) и (1.21) можно утверждать, что x An0 1 x Ax Ax 1 r + 2 +... + n0 1 = r x 1.

r r r Из последнего неравенства и определения нормы линейного оператора получаем, что A 1 r = r ( A) +.

Теорема доказана.

1.6. Операторная форма записи метода Зейделя. Обобщение метода Зейделя.

Запишем исходную систему линейных алгебраических уравнений (1.6) в операторной форме x = Ax + f, (1.26) где A = (aij ), x Rn, f R n. Положим 0... 0 a11... a1n 0 a a 0... 0 0 a22... a2 n A1 = 21 A2 =,. (1.27)............

............

a... 0 0... ann an 2 n1 Выберем произвольным образом начальное приближение x0 R n и образуем последовательные приближения xm+1 по формулам xm+1 = A1 xm+1 + A2 xm + f (m = 0,1,...). (1.28) Приведенные формулы тождественны формулам (1.8), т.е. способ {xm+1} построения последовательности является фактически операторной формой записи метода Зейделя. Пусть I - единичная квадратная матрица, тогда метод (1.28) можно записать в виде (I A1 )xm+1 = A2 xm + f. (1.29) Предполагая, что существует матрица (I A1 ), обратная матрице (I A1 ), формулу (1.29) перепишем в виде xm+1 = (I A1 ) A2 xm + (I A1 ) f, 1 т.е. метод Зейделя фактически можно записать в виде метода последовательных приближений xm+1 = Dxm + f1, (1.30) где D = (I A1 ) A2, f1 = (I A1 ) f.

1 (1.31) Поэтому скорость сходимости метода Зейделя (1.28) совпадает со скоростью сходимости метода последовательных приближений (1.30). При соответствующей нормировке пространства R n, эта скорость сколь угодно близка к скорости сходимости геометрической прогрессии со знаменателем, близким к значению спектрального радиуса r (D) матрицы D. Таким образом, в случае, когда r ( D) r ( A), (1.32) метод (1.30) сходится быстрее метода последовательных приближений. При выполнении равенства r ( A) = r ( D) скорости сходимости двух методов одинаковы.

Пусть, теперь произвольная n n матрица А представлена в виде A = A1 + A2, при этом не обязательно, чтобы А1 и А2 имели треугольную форму (1.27).

Если при этом спектральный радиус матрицы А1 меньше, чем единица:

r(A1)1, (1.33) (I A ) то, как известно [14], существует матрица, обратная к матрице (I A1 ), и поэтому уравнение (1.26) можно записать в эквивалентном виде x = Dx + f1, где D и f1 имеют вид (1.31).

Везде далее в этой главе будем считать выполненным условие r( A ) 1, которое достаточно как для сходимости метода последовательных приближений, так и для сходимости метода Зейделя.

Укажем условия гарантирующие выполнение строгого неравенства (1.32).

Теорема 1.11. Пусть A1, A2 0, и выполняется условие r( A ) 1. Тогда выполняется неравенство r ( D) r ( A), т.е. метод Зейделя определен, и сходится не медленнее, чем метод последовательных приближений для решения уравнения x = Ax + f.

Доказательство. В условии теоремы 0 A1 A, отсюда следует [59], что r ( A1 ) r ( A), (1.34) и в силу этого определена последовательность (1.30). Для доказательства неравенства (1.34) выберем произвольно 0 так, чтобы 0 1 r ( A), и пусть v - вектор с положительными координатами, удовлетворяющий неравенству Av (r ( A) + )v. (1.35) Прежде всего, установим существование такого вектора. Так как конус неотрицательных векторов в R n телесен и нормален [32], то для каждого вектора u0 с положительными координатами определена в R n u0 -норма. Так как в пространстве R n все нормы эквивалентны, то, принимая во внимание равенство r ( A) = lim n An 1, n согласно [66], имеем = r ( A), lim n Anu0 uo n поэтому для числа r ( A) + при 0 найдется такой номер n0, что An u0 [r ( A) + ]u0.

o Положим v = [r ( A) + ] u0 + [r ( A) + ] Au0 +... + [r ( A) + ]An 1u0 + An u0.

no 1 no 2 o o Очевидно, что v - квазивнутренний элемент конуса K, т.е. v 0, и Av [r ( A) + ]v, а это доказывает (1.35). Имеем [r ( A) + ]A v + A2v Av [r ( A) + ]v, откуда A2v (r ( A) + )(I A1 )v.

Применяя к обеим частям последнего неравенства положительный оператор ( I A1 ) 1, получим Dv = ( I A1 ) 1 A2v (r ( A) + )v, отсюда, в виду произвольности 0, следует неравенство (1.34) согласно результатам оценки спектрального радиуса неотрицательной матрицы.

Следствие. Для линейных алгебраических систем с r ( A) 1, А, неотрицательными матрицами у которых A = A1 + A2, где Ai 0 (i = 1,2,...), метод Зейделя всегда осуществим и сходится не медленнее, чем обычный метод последовательных приближений.

§ 2. Достаточное условие, гарантирующее более высокую скорость сходимости метода Зейделя по сравнению с методом последовательных приближений В связи с последним утверждением возникает естественный вопрос о том, в каких случаях метод Зейделя обладает более высокой скоростью сходимости. В общем случае это не всегда имеет место: для алгебраических систем с верхней треугольной матрицей метод Зейделя фактически совпадает с методом последовательных приближений, а поэтому их скорости сходимости одинаковы. Следующая теорема содержит простое и легко проверяемое достаточное условие более высокой скорости сходимости метода Зейделя по сравнению с методом последовательных приближений.

Теорема 1.12. Пусть матрица А1 переводит каждый вектор u0 с A1u положительными координатами в вектор с положительными координатами, т.е. из u0 0 следует, что A1u0 0. Пусть r ( A) 1.

Тогда имеет место строгое неравенство r ( D) r ( A), т.е. метод Зейделя в этом случае гарантирует более высокую скорость сходимости приближений к решению операторного уравнения (1.26) по сравнению с методом последовательных приближений.

Доказательство. Выберем 0 так, чтобы выполнялось неравенство r ( A) + 1.

Пусть u0 0 и Au 0 [r ( A) + ]u 0.

По условию вектор A1u 0 имеет только положительные координаты, поэтому существует такое 0, для которого выполняется неравенство A1u 0 u 0. (1.36) В общем случае можно считать, что 1, т.к. если 1, то, выбирая 0 1, усиливаем неравенство (1.36) A1u0 u0 0u0.

Справедлива следующая цепочка соотношений [r ( A) + ]A u + A u = ( A + A )u [1 r ( A)]A u 10 2 0 1 2 0 (1.37) [r ( A) + ]u [1 r ( A)]u.

0 Введем обозначение = r ( A) + [1 r ( A)]. (1.38) Тогда, на основании (1.37), выполняется неравенство A2u0 (I A1 )u0 [r ( A) + ]A1u0.

Применяя к обеим частям последнего неравенства положительный, а значит, и монотонный оператор ( I A1 ) 1, и, учитывая, что в силу (1.36) ( I A1 ) 1 u0 = A1nu0 u0, n = будем иметь r ( A) + Du0 = ( I A1 ) 1 A2u0 u0 [r ( A) + ] A1nu0 u0 = n = r ( A) + r ( A) = u0 = u0.

1 Подставляя в это неравенство значение из (1.38), найдем r ( A) + + + r ( A) r ( A) r ( A) + Du 0 u0 = u0.

1 Из последнего неравенства в силу теоремы 1.7 об оценке сверху спектрального радиуса неотрицательной матрицы D по ее поведению на векторе u0 c положительными координатами приходим к справедливости неравенства r ( A) + r ( D).

Так как r ( A) 1 и 0 выбрано произвольно, то из последнего неравенства следует, что r ( A) r ( A)(1 ) r ( D) = r ( A).

1 Теорема 1.12 полностью доказана.

Теорема 1.12 допускает развитие на случай, когда у матрицы А1 не обязательно все элементы строго больше нуля. Как и прежде предлагается, что A 0 и r ( A) 1.

Определение 1.3. Оператор А называется u0 -ограниченным снизу, где u0 0 - фиксированный ненулевой элемент конуса K, если для каждого x можно указать такое натуральное m=m(x) и такое = ( x ) 0, для которых выполняется неравенство A m x u 0, и называется u0 -ограниченным сверху, если для каждого х 0 существует такое натуральное n = n(x) и такое = ( x ) 0, что An x u0.

Теорема 1.13. Пусть матрица А1 является u0 -ограниченным сверху + + оператором относительно конуса Rn и для элемента u 0 Rn при некотором 1 0 выполняется неравенство A1u 0 1 u 0.

Тогда r ( D) r ( A).

Доказательство теоремы 1.13 аналогично доказательству предыдущей теоремы. Повторяя рассуждения до соотношения (1.37), получим неравенство A2u0 1 ( I A1 )u0 [r ( A) + 1 ]A1u0, где 1 = r ( A) + [1 r ( A)].

Применим к обеим частям последнего неравенства положительную матрицу ( I A1 ) 1. В результате получим Du0 = ( I A1 ) 1 A2u0 1u0 [r ( A) + 1 ]( I A1 ) 1 A1u0 1u0 1u0 = (1 1 )u0.

где 1 = 1 [r ( A) + 1 ]1 1.

Тем самым r ( D) ( 1 1 ) r ( A), т. к. 1 r ( A), 1 0.

Теорема доказана.

Следствие. В условиях теоремы 1.12 имеет место неравенство r ( A) r ( D). (1.39) Справедливость последнего неравенства проверяется непосредственно.

Неравенство (1.39) позволяет оценить «зазор» между r(A) и r(D) и, тем самым позволяет выяснить эффективность применения метода Зейделя в сравнении с методом последовательных приближений. Этот «зазор» не меньше, чем правая часть неравенства (1.39).

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

Пример. Найдем решение системы 6.25 х1 х2 0.2 х3 = 7. х1 5 х2 + 2.12 х3 = 8. 0.5 х + 2.12 х + 3.6 х = 0. 1 2 Решение. Приведем систему к виду, удобному для построения итераций:

х1 = 0.16 х2 0.08 х3 + 1. х2 = 0.2 х1 0.424 х3 1. х = 0.1389 х 0.5889 х 0. 3 1 В операторной форме преобразованная система примет вид x = Ax + f, 0. 1. 0 0. A = 0.2 0.424, f = 1.736.

где 0 Тогда 0.1389 0.5889 0 0. 0. 0 0. D = 0 0.032 0.4272.

0 0.0033 0. Здесь, r ( A) = 0.7278, r ( D) = 0.4592, r ( D) r ( A) - достаточное условие, гарантирующее более быструю сходимость метода Зейделя, выполняется.

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

Значения приближений по методу последовательных приближений n х1 х2 х 0 0.0000 0.0000 0. 1 1.2000 -1.7360 -0. 2 0.9276 -1.4677 0. 3 0.9020 -1.8850 0. 4 0.8449 -1.8392 0. 12 0.8006 -1.9985 0. 13 0.8003 -1.9993 0. 14 0.8002 -1.9995 0. 15 0.8001 -1.9998 0. Значения приближений по методу Зейделя 1 1.2000 -1.4960 0. 2 0.9088 -1.8288 0. 3 0.8367 -1.9435 0. 4 0.8121 -1.9813 0. 5 0.8040 -1.9938 0. 6 0.8013 -1.9980 0. 7 0.8004 -19993 0. 8 0.8001 -1.9998 0. Заметим, что точные значения решения х1=0.8, х2=-2, х3=1.

В данном случае нам приходится совершать на 7 итераций меньше при расчетах методом Зейделя по сравнению с методом последовательных приближений.

§3. Ускорение сходимости метода Зейделя решения систем линейных алгебраических уравнений Пусть множество конусных отрезков v,w, состоящее из всех таких элементов х, для которых v x w, является инвариантом относительно преобразования def Bx Ax + f, т.е.

v Av + f Aw + f w.

и Предположим, что A = A1 + A2, где Ai 0, A1 и A2 матрицы вида (1.27), r ( A) 1.

Определим приближения vn и wn формулами:

vn +1 = A1vn +1 + A2 vn + f, (n = 0,1,2,...;

v0 = v, w0 = w).

wn +1 = A1wn +1 + A2 wn + f Очевидно v v1 v 2... v n... wn... w2 w1 w. (1.40) Приближения vn и wn являются монотонными, они сходятся к единственному решению х* уравнения x = Ax + f, при этом для каждого n выполняется неравенство v n x wn.

{vn } {wn } сходятся к х* В ряде случаев последовательности и недостаточно быстро. Укажем прием, позволяющий построить новые двусторонние приближения, сходящиеся к х*, вообще говоря, быстрее, чем {vn } и {wn }.

Пусть числа p1 и q1 неотрицательны и удовлетворяют неравенствам v1 v0 p1 ( w0 w1 ), w0 w1 q1 (v1 v0 ). (1.41) Образуем новые элементы v1 + p1 w1 w1 + q1v v1 = w1* =,. (1.42) 1 + p1 1 + q Тогда из равенства (1 + p1 )( Av1 + f v1 ) = ( Av1 + f v1 ) p1 ( w1 Aw1 f ) * * следует (1 + p1 )( Av1 + f v1 ) = ( A2 v1 A2 v0 ) p1 ( A2 w0 A2 w1 ) = = A2 (v1 v0 ) p1 ( w0 w1 ) 0, т.е.

Av1 + f v1 0.

Аналогично доказывается, что w1 Aw1 f 0.

Из последних соотношений имеем v1 v1 x * w1 w1.

* * (1.43) Формулы (1.42) можно рассматривать как шаг рекуррентного процесса построения последовательных приближений vn*, wn* к решению x*. В силу (1.43) этот процесс монотонный, и он сходится не медленнее, чем метод (1.40). Основную трудность составляет отыскание начальных приближений v0 и w0. В [33] указан алгоритм отыскания таких начальных приближений.

Примеры показывают, что, как правило, последовательности {wn*},{vn*} сходятся существенно быстрее, чем последовательности {v n }, {wn }.

Проиллюстрируем эти методы следующими примерами.

Пример 1. Пусть требуется решить уравнение x = Ax + f, где 0.35 0.1 0.15 0.2 0.15 0.1 0.4 0.15 0.05 0.1 A = 0.15 0.2 0.45 0.15 0.05, f = 0.15 0.15 0.2 0.45 0.1 0.05 0.05 0.1 0.15 0.45 Так как сумма элементов каждой строки матрицы А меньше, чем 1, то спектральный радиус матрицы А меньше, чем единица поэтому при любом f это уравнение имеет единственное решение. При заданном f его решением будет вектор 38. 30. x* = 46.949224422.

48. 29. Вычислим приближения xn к решению x по методу последовательных приближений, а приближения vn и wn к точному решению по недостатку и по избытку соответственно по формулам, соответствующим методу Зейделя:

vn+1 = ( I A1 ) 1 A2vn + ( I A1 ) 1 f, xn+1 = Axn + f, wn+1 = ( I A1 ) 1 A2 wn + ( I A1 ) 1 f, где 0 0 0 0.1 0 0 0 A1 = 0.15 0.2 0, 0 0.15 0.15 0.2 0.05 0.05 0.1 0.15 0.35 0.1 0.15 0.2 0. 0 0.4 0.15 0.05 0. A2 = 0 0 0.45 0.15 0.05, 0 0.45 0. 0 0 0. 0 0 v0 = x0 = w0 = (1;

1;

1;

1;

1).

Тогда 1.950 1.950 2. 2.895 2.800 4. v1 = 6.521, x1 = 6.000, w1 = 11.669 ;

6.581 5.050 13. 3.331 1.800 8. 23,804 19.572 35. 19.420 16.161 28. v10 = 31.201, x10 = 26.217, w10 = 43.999 ;

32.232 26.417 45. 19.261 15.121 28. 38.713 37.938 38. 30.409 29.835 30. v50 = 46.596, x50 = 45.770, w50 = 46.849 ;

48.454 47.554 45. 29.773 29.170 29. 38.936 38.932 38. 30.588 30.570 30. = 46.847, = 46.822, = 46.849.

v100 x100 w 48.719 48.691 48. 29.945 29.926 29. Эти данные свидетельствуют о возможности получения довольно узких границ vn, wn для решения х* и о монотонной сходимости этих границ к искомому решению, а в целом - о достаточной эффективности предложенного метода.

При построении приближений с помощью классического метода Зейделя в качестве оценки погрешности приближений на n-ом шаге естественно принять n xn xn 1 = тах xi( n ) xi( n 1).

i В рассмотренном примере 100 0.104.

В случае построения двусторонних приближений погрешность составит 1 wn vn = тах wi( n ) vi( n ).

n 2 2i В нашем случае 0. 100 = 0.0105.

Пример 2. Рассмотрим уравнение x = Ax + f, где 0.2 0.3 A= 0.4 0.2, f =.

Для его решения используем шаг рекуррентного процесса построения последовательных приближений v1, w1 к решению x. Заметим, что точное 19. решение данного уравнения x = 22.307692, а спектральный радиус оператора A : r ( A) = 0.5464.

Пусть x0 =. Тогда векторы v0 и w0 согласно предложенному выше алгоритму, соответственно равны 25 v0 =, w0 =.

25 По формулам (1.42), (1.43) получим приближения vn и wn, между которыми заключено решение исходного уравнения. Соответствующие приближения к решению представим в следующей таблице:

№, n vn wn (17.776595;

20.531914)Т (21.500000;

25.000000)Т (19.124786;

21.685470)Т (20.063157;

22.757894)Т (19.575000;

22.270000)Т (19.648888;

22.355555)Т (19.590081;

22.278662)Т (19.637779;

22.333750)Т (19.614102;

22.306211)Т (19.616522;

22309005)Т (19.615001;

22.307250)Т (19.615724;

22.308084)Т (19.615175;

22.307450)Т (19.615570;

22.307906)Т При этом точность вычислений на 13 шаге составляет 10-3. Отметим, что при отыскании решения данного уравнения методом последовательных приближений для достижения такой точности потребуется совершить итераций.

Рассмотренный выше пример был реализован при помощи программы на языке программирования TURBO PASCAL, разработанной автором совместно с Плютой А.И. (приложение 1).

§4. Некоторые варианты модификации метода Зейделя 4.1. Связь скорости сходимости метода Зейделя с его порядком.

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

Теоретические результаты и вычислительные эксперименты свидетельствуют об увеличении скорости сходимости метода Зейделя с возрастанием его «порядка».

Рассмотрим уравнение (1.26) с матричным оператором А. В [38] было установлено, что для этого уравнения при условии r ( A1 ) 1, метод Зейделя монотонно зависит от выбора матрицы А1, а именно, с возрастанием количества ненулевых элементов матрицы А1 скорость сходимости метода (1.28) возрастает, точнее говоря не уменьшается. Это можно интерпретировать следующим образом: чем большую часть А1 матрицы А мы ( I A1 ) оставляем в обращаемой части уравнения, тем быстрее приближения, полученные по методу Зейделя (1.28), сходятся к решению x.

Уместно, однако, сразу заметить, что с возрастанием «доли» А1, вообще говоря, усложняется процедура определения приближений по методу Зейделя, эта процедура будет самой простой, если в качестве А1 брать нижнюю треугольную часть матрицы А, т.е. полагать i 1 n yi( m +1) = aij y (jm +1) + aij y (jm ) + f i (i = 1, n), (1.44) j =1 j =i что соответствует классической схеме метода Зейделя. Если же присоединить к матрице А1 еще и главную диагональ, то в этом случае метод Зейделя примет несколько нетрадиционный вид:

i n yi( m +1) = aij y (jm +1) + aij y (jm) + f i (i = 1, n), (1.45) j =1 j = i + т.е. примет вид неявной схемы, при которой для определения (m+1)-го приближения по компоненте с номером i, т.е. при определении yi( m+1) необходимо решить для каждого i одно скалярное уравнение с неизвестным yi( m+1). Этот метод назовем методом Зейделя первого порядка.

Соответственно, если в А1 включить еще одну выше расположенную диагональ, параллельную главной, то для определения yi( m+1) придется решать систему двух уравнений с двумя неизвестными yi( m+1) и yi(+1+1).

m Соответствующий метод назовем методом Зейделя второго порядка. По аналоги вводятся методы Зейделя третьего и более высокого порядков. Тем самым, чем «большая» часть матрицы А будет включаться в А1, тем сложнее будет фактическая реализация метода Зейделя, т.к. с «ростом» матрицы А возрастает порядок системы уравнений и, соответственно, усложняется схема реализации метода Зейделя.

В классической схеме метода Зейделя порядок соответствующей системы равен нулю, т.е. никакой системы решать не приходится.

Понятно, что применение неявных схем требует решения вспомогательных систем линейных уравнений. Количество неизвестных в этих системах прямо зависит от порядка метода Зейделя. Оно тем больше, чем выше порядок. В любом случае при применении метода Зейделя невысокого порядка, порядок соответствующей системы, вообще говоря, меньше числа n-порядка исходной системы линейных алгебраических уравнений, и поэтому применение соответствующей схемы является более простым, нежели решение исходной системы n уравнений с n неизвестными.

Итак, метод Зейделя усложняется в реализации с «ростом» матрицы А1, и поэтому, естественно, на эту более сложную схему метода Зейделя имеет смысл идти лишь в том случае, если при этом улучшается скорость сходимости. В условиях теоремы 1.12 метод Зейделя сходится быстрее, чем метод последовательных приближений и как следствие из этой теоремы метод (1.45) сходится, вообще говоря, быстрее, чем метод (1.44).

Рассмотрим в качестве иллюстрации конкретный пример реализации схемы метода Зейделя первого и второго порядков. Введем обозначения:

yi( m ) m -тое приближение к i-той координате yi* решения системы (1.26), полученное с помощью классического метода Зейделя;

yi(,m ) m -тое приближение к i-той координате yi* решения системы (1.26), полученное с помощью метода Зейделя 1-го порядка.

yi(,m ) m -тое приближение к i-той координате yi* решения системы (1.26), полученное с помощью метода Зейделя 2-го порядка.

В этих обозначениях система (1.45) имеет вид i n yi(,m+1) = aij y (jm+1) + aij y (jm ) + (i = 1, n).



Pages:   || 2 | 3 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.