Книги, научные публикации
Pages: | 1 | 2 | -- [ Страница 1 ] --
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РФ СТАВРОПОЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
На правах рукописи
Плюта Алексей Иванович Об итерационных методах решения операторных уравнений второго рода Специальность
05.13.18. - математическое моделирование, численные методы и комплексы программ Диссертация на соискание ученой степени кандидата физико-математических наук
Научный руководитель - доктор физико-математических наук, профессор, член-корреспондент АН Таджикистана, академик МАИ В.Я. Стеценко Ставрополь - 2004 2 ОГЛАВЛЕНИЕ ВВЕДЕНИЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕ. ГЛАВА 1. Обзор литературыЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕ з1. Метод последовательных приближений................................................... з2. Метод ускорения сходимости монотонных приближений к решению уравнения вида x = Ax + f ЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕ.. з3. Метод однопараметрического итеративного агрегирования решения линейных операторных уравнений вида x = Ax + f, где оператор A - матрица n - го порядкаЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕ. з4. Метод однопараметрического итеративного агрегирования решения нелинейных операторных уравнений вида x = F ( x) + f, где F (x) - нелинейный операторЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕ ГЛАВА 2. Построение приближений, сходящихся к спектральному радиусу и собственному вектору линейного оператораЕЕЕЕЕЕЕЕЕ з5. Построение приближений, сходящихся к спектральному радиусу линейного оператораЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕ.. з6. Построение приближений, сходящихся к собственному вектору линейного оператораЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕ.. ГЛАВА 3. Развитие методов построения приближений, сходящихся к точному решению операторного уравнения вида x = Ax + f ЕЕЕЕЕЕ. з7. Об одном итерационном методе решения системы линейных алгебраических уравнений вида x = Ax + f с квадратной матрицей A, в случае, когда спектральный радиус матрицы A, больше чем единицаЕЕЕЕЕ. з8. Получение двусторонних оценок точного решения x* операторного уравнения вида x = Ax + f, в случае, когда спектральный радиус оператора A не обязательно меньше единицыЕЕЕЕЕЕЕЕЕЕЕЕЕЕ. з9. О некоторых подходах к уточнению границ решения операторных уравнений вида x = Ax + f в случае, когда спектральный радиус оператора A не обязательно меньше единицы. з10. УГибридФ методов ускорения сходимости монотонных приближений к решению x* уравнения вида x = Ax + f и однопараметрического итера73 65 56 56 41 32 32 27 21 15 4 8 тивного агрегированияЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕ.. з11. Об одном варианте метода ускорения сходимости монотонных приближений к решению уравнения вида x = Ax + f ЕЕЕЕЕЕЕЕЕЕ.... з12. Об одном варианте метода ЗейделяЕЕЕЕЕЕЕЕЕЕЕЕЕЕ.
86 93 ЗАКЛЮЧЕНИЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕ.. 112 ЛИТЕРАТУРАЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕ 114 ПРИЛОЖЕНИЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕ.. Введение При решении широкого класса задач математического анализа, алгебры, экономики требуется находить решение операторных уравнений. В тех случаях, когда процесс отыскания точного решения является затруднительным, на помощь приходят итерационные методы, позволяющие найти приближенное решение с определенной степенью точности.
x = Ax + f Соответствующий (1) класс задач можно представить с помощью операторного уравнения вида с линейным или нелинейным оператором А, действующим в банаховом пространстве Е, и свободным членом f из этого пространства. Большое практическое значение приобретает возможность строить приближения un и, соответственно, vn к решению x* операторного уравнения вида (1), та кие что un x* vn При этом, оказывается, параллельно решаются две важные задачи теории приближенных методов решения операторных уравнений - задача об оценке погрешности приближенного решения, а также задача об априорной оценке относительной погрешности приближенного решения. Использование современных ЭВМ открывает широкие возможности для решения таких задач. Математическое моделирование стало активно внедряться в практику научных и прикладных разработок при исследовании сложных явлений и процессов, происходящих в экономике. Лишь с помощью современных ЭВМ удается проводить численное моделирование достаточно сложных экономических процессов. Существенные прикладные преимущества, проведенные исследования практической скорости сходимости итерационных процессов к точному решению x* операторного уравнения вида (1), возможность контроля результатов в процессе решения и наличие математических обоснований, дают повод обратить серьезное внимание на итерационные методы не только как на объект интересных тео ретических исследований, но и как на новые подходы к организации и проведению реальных расчетов плановых задач большой размерности и сложной структуры. Актуальность проблемы. Балансовая модель производства является одной из наиболее простых математических моделей. Она записывается в виде системы уравнений, каждое из которых выражает требование равенства (баланса) между количеством продукции, производимой отдельным экономическим объектом, и совокупной потребности в этом продукте. Отсюда происходит название модели. Впервые балансовые модели начали использоваться в СССР в 20-х годах. В более или менее законченном виде теория балансовых моделей была разработана американским ученым В.В. Леонтьевым в середине 30-х годов. Однако в те годы ни уровень развития математической науки, ни качество вычислительной техники не позволили широко распространить балансовый метод. За разработку и внедрение в практику метода межотраслевого баланса группа советских экономистов под руководством академика А.Н. Ефимова в 1968 году была удостоена Государственной премии СССР. В настоящее время большое количество работ посвящается этой модели и ее применению для решения различных задач. Такой интерес к балансовой модели определяется тем, что, как оказалось, эта модель хорошо отображает многие существенные особенности современного производства и в то же время легко поддается расчету. Во многих странах мира балансовый метод используется для экономического анализа, планирования и прогнозирования. В связи с внедрением ЭВМ в научные разработки, значительно повысился интерес к различным численным методам и алгоритмам, реализация которых граничит с проведением вычислительного эксперимента. Потребность в таком подходе к решению задач математической экономики диктуется все усложняющимися запросами практики, а также связана с попыткой создания более рациональных и более общих теоретических моделей для изучения сложных экономических явлений.
Активное использование методов численного моделирования позволяет резко сократить сроки научных и конструкторских разработок. Цели работы - приближенное решение операторных уравнений вида (1) в случаях, когда спектральный радиус ( A) оператора A не обязательно меньше единицы;
построение итерационных последовательностей сходящихся к решению уравнения (1), к собственным значениям и собственным векторам оператора A ;
разработка новых методов, повышающих скорость сходимости итераций к решению уравнения (1);
разработка соответствующего программного обеспечения, позволяющего реализовать предложенные методы. Научная новизна результатов работы. Развитие теории линейных и нелинейных операторов, действующих в полуупорядоченных банаховых пространствах. Так, например, предложены развития методов решения операторных уравнений вида (1) в случаях, когда у оператора A спектральный радиус r ( A) не обязательно меньше единицы. Предложен метод построения двусторонних оценок точного решения x* операторного уравнения вида (1) в случае, когда спектральный радиус оператора A не обязательно меньше единицы. Предложены варианты методов, позволяющие строить приближения к решению уравнений вида (1), обладающие высокой скоростью сходимости. Разработано программное обеспечение на языке программирования TURBO PASCAL, реализующее предложенные итерационные методы. Достоверность результатов работы вытекает из математической строгости постановки и решения исследуемых задач, а также из совпадения ряда полученных результатов в частных случаях с известными в литературе. Практическая значимость работы заключается в возможности применения полученных методов решения уравнения (1) при решении конкретных задач математики и экономики. Отдельные результаты могут быть использованы при чтении специальных курсов и подготовке учебных пособий. На защиту выносятся следующие положения:
- итерационный метод решения системы линейных алгебраических уравнений вида (1) с квадратной матрицей A, в случае, когда наибольшее по модулю собственное значение матрицы A, больше чем единица;
- методы получения двусторонних оценок точного решения x* операторного уравнения вида (1), в случае, когда спектральный радиус оператора A не обязательно меньше единицы, а также подходы к уточнению полученных оценок;
- синтез методов ускорения сходимости монотонных приближений к решению x* уравнения вида (1) и однопараметрического итеративного агрегирования;
- метод ускорения сходимости монотонных приближений к решению уравнения вида (1), в случае выбора в качестве начальных приближений векторов, которые ограничивают точное решение x* уравнения вида (1) сверхул и снизу;
- вариант метода Зейделя, позволяющий строить приближения, сходящиеся к точному решению x* уравнения (1) с помощью метода ускорения сходимости. Структура и объем диссертации. Диссертация состоит из введения и трех глав, заключения, списка литературы и приложения. В ней принята сквозная нумерация параграфов, для утверждений и формул введена двойная нумерация, включающая номер параграфа и порядковый номер утверждения или формулы в нем. Диссертация изложена на 167 страницах, список использованной литературы содержит 82 наименования.
ГЛАВА 1. ОБЗОР ЛИТЕРАТУРЫ з1. Метод последовательных приближений Одним из наиболее известных итерационных методов решения систем линейных уравнений является метод последовательных приближений [4] (метод простой итерации). Система уравнений Ax = b тем или иным методом преобразуется к виду уравнения Увторого родаФ:
x = Bx + f (1.1) после чего его решение находится как предел последовательности xm +1 :
xm +1 = Bxm + f, (m = 0,1,2,...) (1.2) где B - матрица порядка (n n), f - свободный вектор, f R n, x - неизвестный вектор, x R n, x0 - начальное приближение. Метод (1.2) называется методом простой итерации. Теорема 1.1. (о достаточном условии сходимости метода простой итерации) Если норма матрицы B меньше единицы: B < 1, то система уравнений (1.1), при любом свободном члене f R n, имеет единственное решение и итерационный процесс (1.2) геометрической прогрессии:
x* xm +1 c x1 x0 B, m сходится к решению x* = x* ( f ) со скоростью m = 0,1,2,..., c const.
Качество итерационного процесса удобно характеризовать скоростью убывания отношения погрешности после m итераций к начальной погрешности:
S m = sup || xm || || B m x0 || = sup =|| B m ||. x 0 0 || x0 || x 0 0 || x0 || m Можно гарантировать, что величина S m, если B, т.е. при m m = ln( 1 ). ln(|| B ||1 ) Если существуют постоянные, такие, что при x 9 || x|| || x||, || x||, || x|| то нормы x и x в R n называются эквивалентными. Имеем m m || r m || || r m || || B|| || r 0 || || B|| || r 0 ||.
Таким образом, если условие изложенной выше теоремы выполнено для нормы., то утверждение справедливо относительно любой эквивалентной ей норме. Любые две нормы в конечномерном пространстве являются эквивалентными. В частности, нормы x 1, x 2, x, вычисляемые соответственно по формулам, || x||1 = |x |, j j = m || x||2 = |x | j j = m, || x || = max | x j | 1 j m эквивалентны между собой вследствие справедливости цепочки неравенств x x 2 x 1 m x.
Определение 1.1. Норма A называется согласованной с нормой x в пространстве, если для каждого x из пространства векторов выполняется Ax c x, где с-const. Согласованные с вышеперечисленными нормами в пространстве матриц являются соответственно нормы A 1 = max ( | aij |), 1 j m i =1 m m A 2 = max i( A* A), 1 i m A = max( | aij |), 1 i m j = где iD - собственные значения матрицы D = A* A, а A* - матрица, сопряженная к матрице A (т.е. это результат комплексного сопряжения к матрице транспонированной по отношению к матрице A ). При решении уравнения вида (1.1) методом последовательных приближений (1.2) по заданной точности > 0 вычислений бывает важно определить число итераций "m". Поясним как найти m - количество итераций, обеспечи вающих, для получения искомого решения системы (1.1), приближение к решению с точностью до. При известных условиях к решению уравнения (1.1) сходится итерационный процесс (1.2), при любом начальном приближении x0, при этом таковыми известными условиями является одно из следующих условий: a) б) max aij q1 <1;
i = 1, n j = 1 n n max a ji q2 <1;
i = 1, n j = в) a i =1 j = n n 2 ij q 3 <1.
Пусть > 0 заданное число, тогда для того чтобы гарантировать неравенство:
x xm+ * (i ) qim x1 x0 1 qi (i ) <, (i = 1,2,3) где x (i ) соответственно одна из следующих норм:
x ( 1) = max xi, x i = 1, n = i = n xi, x 3 = x i = n 2 i, положив ln z= (1 qi ) x1 x0 ln(qi ) (i ), достаточно определить m по формуле:
m = [z ] + 1, где [z ] обозначает целую часть числа z (наибольшее целое число, не превосходящее z ). Отметим явные преимущества метода последовательных приближений:
- относительная простота построения последовательности xm, сходящейся к решению уравнения (1.2) ;
- легкость реализации метода на ЭВМ. Недостатками метода последовательных приближений является, вообще говоря, недостаточно высокая скорость последовательных приближений (1.2), к решению уравнения (1.1), особенно в тех случаях, когда наибольшее по модулю собственное значение матрицы B, близко к единице. Рассмотрим соответствующие примеры, когда по заданной точности определяется количество приближений к вектору являющимся решением данной системы уравнений. В примере 1 выполняются все три условия (а,б,в). Пример 1. Рассмотрим систему уравнений вида (1.1), где. 0.4 0.4 01 B = 0.3 0.2 0.4,.. 01 012 0.3 1 f = 1. * 5.337423 Заметим, что значение точного решения x = 4.754601 3.006134 а спектральный радиус оператора B : r ( B) = 0.7707. Используем метод (1.2). В качестве на 1 чального приближения выберем вектор x0 = 1. Пусть = 0.0001. Получен ные значения последовательных приближений представим в виде таблицы. Таблица 1 № п/п, m 1 2 4 10 17 28 42 1.900000 2.672000 3.750516 5.004784 5.283694 5.334361 5.337343 Значения приближений xm 1.900000 2.558000 3.450924 4.481399 4.710473 4.752086 4.754535 1.520000 1.874000 2.336384 2.865818 2.983470 3.004843 3. 52 5.337417 5. 4.754596 4. 3.006132 3. На основании сказанного выше, имеют место оценки близости x* xm 2 < В данном примере m = 53. Рассмотрим пример в котором не выполняется условие а). Пример 2. Рассмотрим систему уравнений вида (1.1), где 0.4 0.6 0.1 B = 0.3 0.2 0.4, 0.1 0.12 0.3 1 f = 1. * 8.681318 Заметим, что значение точного решения x = 6.387362 3.763736 а спектральный радиус оператора B : r ( B) = 0.8404. Используем метод (1.2). В качестве начального приближения выберем 1 вектор x0 = 1. Определим = 0.0001. Полученные значения последователь ных приближений представим в виде таблицы. Таблица 2 № п/п, m 1 2 8 10 20 42 62 130 152 2.100000 3.132000 6.723696 7.298678 8.438316 8.676017 8.681154 8.681318 8.681318 Значения приближений xm 1.900000 2.618000 5.059942 5.449825 6.222588 6.383767 6.387251 6.387362 6.387362 1.520000 1.894000 3.106727 3.299700 3.682180 3.761957 3.763681 3.763736 3. В данном примере m = 152. На основании сказанного выше, имеют место оценки близости x* xm 2 <. Рассмотрим пример, в котором выполняется лишь условие в). Пример 3. Рассмотрим систему уравнений вида (1.1), где 0.4 0.6 0.1 B = 0.3 0.2 0.4, 0.1 0.2 0.3 * 1 f = 1. 10 Заметим, что значение точного решения x = 7.5, а спектральный радиус оператора B : r ( B) = 0.8662. Используем метод (1.2). В качестве начального приближения выберем 1 вектор x0 = 1. Определим = 0.00001. Полученные значения последователь ных приближений представим в виде таблицы. Таблица 3 № п/п, m 1 2 8 25 60 100 491 777 2.100000 3.140000 7.098880 9.747447 9.998342 9.999994 10.00000 10.00000 Значения приближений xm 1.900000 2.650000 5.451648 7.321683 7.498829 7.499996 7.500000 7.500000 1.600000 2.070000 3.764142 4.892414 4.999293 4.999997 5.000000 5. В данном примере m = 777. На основании сказанного выше имеют место оценки близости x xm 3 <. Проиллюстрируем пример у которого не выполняется ни одно из данных условий (а,б,в).
Пример 4. Рассмотрим систему уравнений вида (1.1), где 0.4 0.6 0.1 B = 0.3 0.2 0.4, 0.1 0.3 0.3 1 f = 1. 12.474226 Заметим, что значение точного решения x* = 9.587628, а спектральный 7.319587 радиус оператора B : r ( B) = 0.8973. Используем здесь метод (1.2). В качестве начального приближения выбе 1 рем вектор x0 = 1. После выполнения соответствующих действий замечаем, что ни одно из данных условий не выполняется. При решении данного примера методом последовательных приближений получим итерационный процесс, сходящийся к точному решению x*, но, используя, изложенный выше метод мы не можем определить количество итераций по заданной наперед точности. Отметим, что проиллюстрированные выше примеры были реализованы при помощи разработанной автором программы на языке программирования TURBO PASCAL. Из приведенных примеров видно, что для одного и того же, номер приближений, начиная с которого выполняется неравенство, бывает различным, а это говорит о том, что для достижения одной и той же точности для приближения к искомому вектору решения заданной системы уравнений приходится совершать различное количество приближений. В этой связи уместно ввести характеристику, которую можно назвать скоростью сходимости метода последовательных приближений. Эта скорость определяется числом тех итераций, которые необходимо совершить для того, чтобы соответствующие приближения xm +1 отличались от точного решения x* меньше чем на. Оказывается [10], что эта скорость определяется величиной спектрального радиуса r (B) матрицы B.
з2. Метод ускорения сходимости монотонных приближений к решению уравнения вида x = Ax + f Рассмотрим операторное уравнение вида x = Ax + f, (2.1) где A - линейный положительный оператор относительно телесного нормального конуса K в банаховом пространстве E, f некоторый вектор из E. Предположим, что спектральный радиус r ( A) < 1 ;
в этом случае уравнение (2.1) имеет единственное решение x*, которое является пределом последовательных приближений xn +1 = Axn + f, (n = 0,1,2,...) при любом начальном приближении x 0 E. Допустим, что начальное приближение x 0 = u 0 выбрано так, что u0 Au0 + f.
(2.2) Тогда последовательные приближения un +1 = Aun + f будут удовлетворять соотношениям u 0 u1... u n u n +1... x *. (2.3) Аналогично, если начальное приближение x 0 = v 0 удовлетворяет соотношению v0 Av0 + f, (2.4) то последовательные приближения vn +1 = Avn + f удовлетворяют соотношениям x *... v n +1 v n... v1 v 0. (2.5) Таким образом, если удается найти элементы u 0 и v 0, удовлетворяющие соответственно соотношениям (2.2) и (2.4), то мы получаем монотонные приближения по избытку и по недостатку к точному решению x * операторного уравнения (2.1). Наличие двусторонних монотонных приближений дает одновременно оценку погрешности: если приближенным значениям решения x * считать элемент 1 (u n + v n ), то из (2.3) и (2.5) вытекает двусторонняя оценка 1 (v n u n ) 1 (u n + v n ) x * 1 (v n u n ). 2 2 Из этой оценки, как правило, нетрудно получить оценку для норм разности x* vn,. x* un.
Основную трудность составляет отыскание начальных приближений u 0 и v 0. В [36] указан алгоритм отыскания таких начальных приближений.
Конечно, в различных частных случаях элементы u 0 и v 0 можно выбирать более простым способом. Например, если f K, то в качестве u 0, конечно, можно выбрать элемент f. Пусть u 0 и v 0 удовлетворяют соответственно соотношениям (2.2) и (2.4). Будем считать дополнительно, что выполнены неравенства u1 u 0 p1 (v 0 v1 ), v 0 v1 q1 (u1 u 0 ), где одно из чисел p1 и q1 положительно (при p1 = q1 = 0 эти неравенства совпадают с (2.2) и (2.4) ). Определим тогда элементы * u1 = u1 + p1 v1, 1 + p1 v1 + q1u1. 1 + q (2.6) (2.7) * v1 = Справедлива следующая теорема [36]. Теорема 2.1. Справедливы соотношения * * u1 u1 x * v1 v1.
(2.8) Формулы (2.6) и (2.7) можно рассматривать как рекуррентный процесс * * построения последовательностей u n, v n. Теорема 2.1 означает, что этот рекур рентный процесс сходится не медленнее последовательностей (2.3) и (2.5), и сохраняет монотонность последовательных приближений. Многочисленные примеры показывают, что при достаточно общих условиях процесс (2.6) и (2.7) сходится существенно быстрее обычного метода последовательных приближений. Проиллюстрируем рассмотренный выше метод ускорения сходимости соответствующими примерами. Пример 1. Пусть дано уравнения вида x = Ax + f, где 0.2 0.3 A=, 0.4 0.2 9 f =. 10 19. Точное решение данного уравнения x * = 22.307692, а спектральный ра диус оператора A : r ( A) = 0.5464. Пусть z 0 =. Тогда искомые векторы u 0 и v0, согласно предложенному выше алгоритму соответственно равны 25 u0 =, 25 25 v0 =. 25 1 * * Используя вышеизложенный метод, получим приближения un и vn, между которыми заключено решение исходного уравнения.
* * Соответствующие приближения un и vn, к координатам вектора решения представим в виде таблицы. Таблица 4 Приближения к 1-ой координате вектора решения №, n * У un Ф * У vn Ф 1 2 17.776595 19.124786 19. 21.500000 20.063157 19. 5 10 12 13 1 2 3 5 10 12 19.590081 19.614102 19.615001 19.615175 20.531914 21.685470 22.270000 22.278662 22.306211 22.307250 22. 19.637779 19.616522 19.615724 19.615570 25.000000 22.757894 22.355555 22.333750 22.309005 22.308084 22.307906 вычислений на 13 шаге составляет 10-3.
Приближения к 2-ой координате вектора решения Как видно из таблицы точность Отметим тот факт, что при отыскании решения данного уравнения методом последовательных приближений (см.з1) для достижения такой точности потребуется совершить 30 итераций. Пример 2. Пусть дано уравнение вида x = Ax + f, где.. 01 01 0.7 0.01.. 0.5 0.05 015 015, A= 0.2 0.7 0.02 0.08 0.8 0.2 0.3 0.3 1 2 f =. 3 Точное решение:
191.056645 * 194.439858. x= 211151244.. Заметим, что спектральный радиус матрицы A : r ( A) = 0.9899 достаточно близок к числу 1.
19 1 2 Пусть z0 =. Тогда искомые векторы u 0 и v0, согласно предложенному 3 алгоритму, соответственно равны:
40286.255084 40814.407850 u0 =, 44113.308750 76611.114187 40286.255084 40814.407850 v0 =. 44113.308750 76611.114187 * * Используя вышеизложенный метод, получим приближения un и vn, между которыми заключено решение исходного уравнения.
* * Соответствующие приближения un и vn, к координатам вектора решения представим в виде таблицы. Таблица 5 Приближения к 1-ой координате вектора решения №, n * У un Ф * У vn Ф 1 30 400 500 800 1221 1500 2000 1 30 400 -38878.481325 -9218.280631 -26.957225 112.248339 187.334137 191.005313 191.053642 191.056626 -39402.665953 -9361.829864 -26.978429 114. 40071.486916 9571.871840 408.409659 269.626061 194.767868 191.107820 191.059638 191.056663 40613.759665 9721.742109 415.186970 274. Приближения к 2-ой координате вектора решения 800 1221 1500 2000 1 30 400 500 800 1221 1500 2000 1 30 400 500 800 1221 1500 190.659221 194.387724 194.436808 194.439839 -42673.917726 -10125.634450 -28.351559 124.575055 207.061821 211.094852 211.147945 211.151223 -74917.128645 -17806.713604 -51.043768 217.871592 362.921284 370.013210 370.106572 370. 198.209034 194.491833 194.442897 194.439876 43987.251206 10516.603526 449.928053 297.464998 215.228271 211.207464 211.154532 211.151264 77220.207697 18491.839792 789.991882 521.891671 377.281662 370.211233 370.118154 370. Приближения к 3-й координате вектора решения Приближения к 4-ой координате вектора решения Итак, на 2000 шаге точность вычислений составляет 10-4. Рассмотренные выше примеры были реализованы при помощи, разработанной автором программы на языке программирования TURBO PASCAL.
з3. Метод однопараметрического итеративного агрегирования решения линейных операторных уравнений вида x = Ax + f, где оператор A матрица n - го порядка В этом параграфе мы изложим еще один приближенный метод решения систем алгебраических уравнений, позволяющий строить приближения к решению уравнений методом однопараметрического итеративного агрегирования. Соответствующий метод изложен в монографии [25] и является удобным и эффективным методом приближенного решения уравнений вида (2.1). Рассмотрим уравнение вида (2.1) x = Ax + f, где A - матрица порядка (n n), f - свободный вектор, f R n, x - неизвестный вектор, x R n. Предполагается, что f 0 и что спектральный радиус r ( A) матрицы A меньше единицы:
r ( A) < 1.
В этих условиях, как хорошо известно, уравнение (2.1) имеет и притом единственное неотрицательное решение x = x *, к которому сходится обычный метод последовательных приближений. Если r ( A) не удовлетворяет данному условию, то широко известный метод последовательных приближений не позволяет построить приближения, сходящиеся к точному решению x* уравнения (2.1). В такой ситуации важную роль приобретают другие численные методы решения уравнения вида (2.1). К числу таких методов относят так называемые методы итеративного агрегирования. По поводу которых, сразу можно отметить, что для их сходимости совсем не обязательно выполнение условия r ( A) < 1 (т.е. методы итеративного агрегирования сходятся в частных случаях, когда r ( A) > 1 ). Ниже предлагается и исследуется способ, изложенный в [17], построения приближений {x n } к решению x *, являющийся развитием метода итеративного агрегирования в задачах математической экономики.
Рассмотрим скалярное уравнение t l 0 ( x0 ) = t l 0 ( Ax0 ) + l 0 ( f ), (3.1) где l 0 - некоторый неотрицательный выбранный функционал агрегирования, а x0 - выбранное начальное приближение к решению x * и пусть t = t (x0 ) - решение этого уравнения (если оно существует). Заметим, что для однозначной разрешимости уравнения (3.1) достаточно выполнения условия A*l0 l0, < 1. (3.2) Решение уравнения (3.1), в случае если l 0 (x0 ) l 0 ( Ax0 ) 0 выражается формулой t (x0 ) = l0 ( f ) l0 ( f ) =. l 0 ( x0 ) l 0 ( Ax0 ) (l 0 A*l 0 )( x0 ) Определим теперь оператор F (x ) равенством F ( x ) = t ( x ) Ax + f.
Имеют место следующие утверждения [17]. Лемма 3.1. Пусть выполнено условие (3.2). Тогда для каждого x > 0 определено значение оператора F (x ) и для x > 0 выполняется неравенство F (x ) f.
Следствие. Если x0 > 0, то определена последовательность {x n }:
x n +1 = F (x n ), (n = 0,1,2,...) (3.3) причем x n +1 f.
Всюду здесь предполагается выполненным условие (3.2). Лемма 3.2. Функционал t (x ) и оператор F (x ) непрерывны в каждой точке x > 0.
Лемма 3.3. В области x f > выполняется неравенство 23 t (x ) 1. Лемма 3.4. Оператор F (x ) удовлетворяет в области x1 f, x 2 f условию Липшица:
F ( x1 ) F ( x 2 ) 1 [c1 x1 1 +q] x1 x2 1, где c1, q - const. Теорема 3.1. Пусть выполнено неравенство q= 1 A1 < 1.
Тогда последовательность (3.3) сходится к решению x * уравнения (2.1) при любом начальном приближении x0 f. Рассмотрим соответствующие примеры. Пример 1. Рассмотрим систему вида (2.1), а именно x = Ax + f, где 0.01 0.1 0.15 A = 0.2 0.18 0.11, 0.12 0.09 0.07 1.932344 Точное решение x = 3.420915. 3.806197 * 1 f = 2. Спектральный радиус оператора A равен r ( A) = 0.3491. В качестве начального приближения к вектору решения системы уравнений вида (2.1) возьмем 3 вектор x0 = 3. Полученные значения приближений по методу однопарамет рического итеративного агрегирования представим в виде таблицы. Таблица 6 №, n ( x n1) Значения приближений x n ( x n2) ( x n3) 1 2 4 8 10 12 10-6.
1.791878 1.947898 1.932529 1.932345 1.932344 1. 3.492385 3.415026 3.420841 3.420915 3.420915 3. 3.852792 3.801422 3.806139 3.806197 3.806197 3. Как видно из таблицы уже на 12 шаге точность вычисления составляет Отметим также, что и в некоторых случаях когда r ( A) > 1, метод однопараметрического итеративного агрегирования может сходится к решению уравнения вида (2.1). Пример 2. Рассмотрим систему уравнений вида (2.1), где 0.1 0.2 A = 0.3 0.1 0.2 0.2 0.3 0.1 0.1 0.4 0.1 0.4 0.2 0.4 0.1 0.3 0.5 0.4 0.1 0.1 0.4 0.3 0.1, 0.2 0.1 1 2 f = 3. 4 25.645350 39.107519 Точное решение x * = 22.258140. 17.519325 21.944249 Спектральный радиус оператора A равен r ( A) = 1.1256. В качестве начального приближения к вектору решения системы уравнений вида (2.1) возьмем 1 1 вектор x0 = 1. Полученные значения приближений по методу однопарамет 2 рического итеративного агрегирования представим в виде таблицы. Таблица 7 №, n Значения приближений x n ( x n1) ( x n2) ( x n3) ( x n4) ( x n5) 1 2 6 10 14 19 -24.384615 -25.930732 -25.626347 -25.645331 -25.645352 -25.645350 -25. -30.307692 -43.561306 -39.062892 -39.107303 -39.107525 -39.107519 -39. -16.615384 -27.143312 -22.240283 -22.257782 -22.258144 -22.258140 -22. -12.153846 -19.443471 -17.472515 -17.519409 -17.519330 -17.519325 -17. -8.846154 -27.233280 -21.900795 -21.943912 -21.944256 -21.944249 -21. Как видно из таблицы 20 итераций метода однопараметрического итеративного агрегирования дают точность вычислений при определении неизвестного решения порядка 10-6. По сравнению с предыдущим примером заметно снизилась скорость приближения к решению уравнения вида (2.1) (это связано с тем, что в этом примере увеличилось значение r ( A) ). Покажем на соответствующем примере, что приближения, полученные с помощью метода однопараметрического итеративного агрегирования, могут сходиться к решению уравнения вида (2.1) и в том случае, когда спектральный радиус намного больше единицы. Пример 3. Рассмотрим систему уравнений вида (2.1), где 0.9 0.8 A= 0.81 0.6 0.8 0.7 0.6 0.5 0.4 0.5, 0.6 0.7 0.4 0.2 0.51 0.42 1 2 f =. 3 3.692044 1.588537 * Точное решение x =. 1.316427 1.371875 Спектральный радиус оператора A равен r ( A) = 2.4409. В качестве начального приближения к вектору решения системы уравнений вида (2.1) возьмем 26 3 4 вектор x0 =. Полученные значения приближений по методу однопарамет 4 рического итеративного агрегирования представим в виде таблицы. Таблица 8 №, n ( x n1) Значения приближений x n ( x n2) ( x n3) ( x n4) 1 2 5 9 10 -4.648855 -3.826261 -3.694028 -3.692045 -3.692044 -3. -2.071246 -1.709944 -1.590200 -1.588538 -1.588537 -1. -1.697201 -1.328899 -1.316609 -1.316427 -1.316427 -1. 0.783715 1.247948 1.371591 1.371875 1.371875 1. Как видно из таблицы на 11-м шаге точность вычисления достигается 10-6. Отметим, что хорошо известный нам метод последовательных приближений в этом случае не применим. Рассмотренные выше примеры были реализованы с помощью разработанной автором программе на языке программирования TURBO PASCAL. Дальнейшим развитием метода однопараметрического итеративного агрегирования является так называемый метод многопараметрического итеративного агрегирования [25]. Обратим внимание на то, что метод многопараметрического итеративного агрегирования обеспечивает, вообще говоря, более высокую скорость сходимости приближений, по сравнению с однопараметрическим итеративным агрегированием, однако в нем на каждом шаге приходится решать не одно уравнение с одним неизвестным, а систему из нескольких уравнений с соответствующим числом неизвестных. В этом случае естественно УрисунокФ метода усложняется, но при этом мы выигрываем в скорости сходимости.
з4. Метод однопараметрического итеративного агрегирования решения нелинейных операторных уравнений вида x = F ( x) + f, где F (x) - нелинейный оператор. Заметим, что метод однопараметрического итеративного агрегирования применим также и для решения нелинейных систем алгебраических уравнений. Рассмотрим аналог метода итеративного агрегирования для случая нелинейных уравнений вида x = F ( x) + f, (4.1) с нелинейным оператором F (x). Примером таких уравнений может, например, служить следующая система уравнений:
1 1 5.. x = 01( x ) + 01( y ) 3 + 1 1 y = 0.01x + 0.2 ( y ) 3 + Если воспользоваться методом итеративного агрегирования (в его нелинейном варианте), изложенным в [67], т.е. перейти от уравнения (4.1) к следующему уравнению:
tl 0 ( x 0 ) = tl 0 [F ( x0 )] + l 0 ( f ), где l 0 - некоторый выбранный функционал агрегирования, а x0 - выбранное начальное приближение, с неизвестной скалярной величиной t ( x0 ), а затем определить значение t ( x0 ) :
t ( x0 ) = l0 ( f ), l 0 ( x 0 ) l 0 [ F ( x 0 )] при условии что l0 ( x0 ) l0 [F ( x0 )] 0. Тогда можно определить следующее приближение x1 по формуле:
x1 = ( x0 ) = t ( x0 ) F ( x 0 ) + f.
def Аналогично, по индукции положим:
x n +1 = ( x n ) = t ( x n ) F ( x n ) + f. (4.2) Последовательность (4.2) определяет алгоритм метода итеративного агрегирования, в случае нелинейного операторного уравнения. Пусть для любых x выполнено условие:
[c F ( x) + q(t ( y))] q где q таково, что выполнено < 1, (4.3) F (x ) F ( y ) q x y.
Теорема 4.1. Пусть выполнено условие (4.3). Тогда уравнение (4.1) имеет и притом единственное решение x *, и к этому решению сходятся последовательные приближения (4.2). Заметим, что в случае, когда F (x) - линейный оператор, этот метод совпадает с изложенным в з3 методом итеративного агрегирования. Если же F (x) нелинейный оператор, то здесь фактически предлагается новый вариант метода, а именно нелинейный вариант метода итеративного агрегирования. В работе [67] получены достаточные условия сходимости нелинейного варианта метода итеративного агрегирования. Рассмотрим примеры. Пример 1. Рассмотрим нелинейную систему вида x = 0.01x + 0.02 y 0.5 + 0.01z 0.25 + 3 0.5 0.25. 0.1 y = 0.03x + 0.01y + 01z + 4 z = 0.01x 0.25 + 0.2 y 0.5 + 0.4 z 0.5 + Точное решение: x*=3.087732, y*=4.187488, z*=6.437405.
2 В качестве начального приближения выберем вектор x0 = 2. Полученные значения приближений представим в виде таблицы. Таблица 9 №, n xn Значения приближений yn zn 3. 4. 7. 2 4 6 7 до 10-6.
3.083696 3.087717 3.087732 3. 4.176646 4.187447 4.187488 4. 6.397830 6.437256 6.437404 6. Как видно из таблицы уже на 6-м шаге точность вычислений достигается При реализации метода итеративного агрегирования возможно появление приближения, содержащего комплексные числа. В этом случае метод фактически нереализуем. Приведем пример соответствующий этому случаю. Пример 2. Рассмотрим нелинейную систему вида x = 0.9 x 0.5 + 0.8 y 0.25 + 1 0.5 y = 0.7 x + 0.9 y + В качестве начального приближения возьмем вектор x0 =. Полученные 3 значения приближений представим в виде таблицы. Таблица 10 №, n 1 2 -8.965667 комплексное число Значения приближений -13.928957 комплексное число Как видно из таблицы на 2-м шаге вычислений появляются комплексные числа. Предложенный метод на данном примере нереализуем. При реализации метода итеративного агрегирования возможны, также, такие случаи, когда на нечетном шаге наблюдается приближение УснизуФ к вектору решения, а на четном шаге наблюдается приближение УсверхуФ к вектору решения. Приведем пример соответствующий этому случаю. Пример 3. Рассмотрим нелинейную систему вида 0,5 x = 0.5 x + 0.5( y ) + 1 y = 0.9 x 0.5 + В качестве начального приближения возьмем вектор x0 =. Полученные 3 значения приближений представим в виде таблицы. Таблица 11 №, n xn Значения приближений yn 1 2 6 7 12 24 25 30 3.280364 3.824302 3.699622 3.613336 3.655982 3.649138 3.648906 3.649022 3. 2.502408 2.893678 2.764530 2.687309 2.725457 2.719333 2.719125 2.719229 2. Точное решение данной системы уравнений: x=3.649003 и y=2.719212. Как видно из таблицы на 30-м шаге наблюдается сходимость к решению до 4-го знака. Интересно отметить, что в процессе реализации предложенного метода итеративного агрегирования возможна такая ситуация, когда на первый взгляд метод сходится, однако наблюдается сходимость к вектору, не являющемуся решением системы. Приведем соответствующий пример. Пример 4. Рассмотрим нелинейную систему вида x =| y|0.5 +0.2| z|0.5 +1 0.3. 0.5 y = 01| x| +0.3| y| +0.5| z|+2 z =| x|0.25 +0.5| y|+5| z|0.5 + В качестве начального приближения к вектору решения возьмем вектор 1 x0 = 2. Полученные приближения представим в виде таблицы. Таблица 12 №, n xn Значения приближений yn zn 1 2 6 24 30 -0.259054 0.637854 0.210033 0.151685 0.151675 0. 0.591686 1.209162 1.314923 1.328081 1.328082 1. -4.623341 -0.551321 -1.283281 -1.479733 -1.479756 -1. После соответствующей проверки замечаем что вектор, к которому сходятся значения приближений по методу однопараметрического итеративного агрегирования не является решением данной системы уравнений. Из этого следует, что сам факт сходимости еще не гарантирует, что значения приближений сходятся именно к решению данной системы уравнений. Рассмотренные выше примеры были реализованы при помощи разработанной автором программы на языке программирования TURBO PASCAL.
ГЛАВА 2. АЛГОРИТМЫ ПОСТРОЕНИЯ ПРИБЛИЖЕНИЙ, СХОДЯЩИХСЯ К СПЕКТРАЛЬНОМУ РАДИУСУ И СОБСТВЕННОМУ ВЕКТОРУ ЛИНЕЙНОГО ОПЕРАТОРА з5. Построение приближений, сходящихся к спектральному радиусу линейного оператора Знание нормы оператора, а точнее говоря информации о том, что норма оператора меньше единицы, позволяет строить приближение к решению уравнения с этим оператором. Однако, величина нормы оператора существенно зависит от того, каким образом введена норма в соответствующим пространстве. Один и тот же оператор может иметь разные нормы, в зависимости от способа введения нормы в пространстве, при этом не исключено, что одна норма будет меньше единицы, а другая больше единицы. Поэтому возникает принципиальный вопрос о том, в каких случаях можно гарантировать существование эквивалентной нормы [36] в пространстве, в которой норма оператора будет меньше единицы. В силу неоднозначности введения нормы в пространстве, возникает необходимость иметь какую-нибудь общую характеристику, знание которой будет давать информацию о сходимости итерационного процесса к точному решению операторного уравнения. Одной из таких характеристик является спектральный радиус оператора A, который тесно связан с понятием спектра оператора A [36]. Часть предыдущего материала, а также и дальнейшее изложение материала тесно связано с понятием спектрального радиуса оператора A [36]. Пусть A - линейный оператор в n-мерном пространстве E n. Число называется собственным значением оператора A, если уравнение Ax = x имеет ненулевое решение. Совокупность всех собственных значений называется спектром оператора A, а все остальные значения называются регулярными значениями оператора A. Иначе говоря, есть регулярное значе ние, если оператор ( A I ) имеет ограниченный обратный оператор. В конечномерном пространстве возможны два случая: 1) уравнение Ax = x имеет ненулевое решение, т.е. есть собственное значение для A, оператора ( A I )1 при этом не существует;
2) существует ограниченный оператор ( A I )1, т.е. есть регулярная точка. Определение 5.1. Пусть A - собственное значение оператора A. Положим r ( A) = sup A величина r ( A) - называется спектральным радиусом оператора A. Сразу отметим следующий очевидный результат [36]: если у оператора A есть собственное значение, такое что > 1, то при любой эквивалентной нормировке пространства норма оператора больше единицы. Выше уже отмечалось, что для существования у системы уравнений (2.1) неотрицательного решения x* = x* ( f ) для заданного неотрицательного вектора f достаточно, чтобы выполнялось неравенство:
r ( A) < 1, где r ( A) - спектральный радиус матрицы А. В этой связи отметим следующую теорему [4]. Теорема 5.1. Пусть A - линейный оператор, действующий в банаховом пространстве Е, r ( A) - спектральный радиус оператора A, >0 - произвольно заданное число. Тогда в пространстве Е можно ввести новую норму x, эквивалентную заданной норме пространства Е и такую, что будет выполняться неравенство:
A r ( A) +.
Следствие. Для существования в пространстве Е по отношению к заданному оператору A - эквивалентной нормы, такой, что выполняется неравенство:
A < достаточно, чтобы выполнялось неравенство r ( A) < 1. Это следствие позволяет ответить на вопрос, в каких случаях можно рассчитывать на то, чтобы оператор A был оператором сжатия. Тем самым вопрос о том, существует ли такая эквивалентная норма, в которой будет оператор A - оператором сжатия сводится к вопросу об оценке сверху спектрального радиуса r ( A) - этого оператора. Отметим, что проблеме оценок спектрального радиуса оператора r ( A) как сверху, так и снизу, посвящены многочисленные результаты [34], [36], [38], [39],[66]. В этой связи важную роль играют двусторонние оценки для значений спектрального радиуса r ( A) линейного положительного оператора A. Для получения этих оценок можно воспользоваться следующими результатами [36]. Теорема 5.2. Пусть u0 R n - вектор у которого все компоненты (u0 )i (i=1,2,..n) являются положительными числами: (u0 )i > 0. Пусть 0 и 0 таковы, что u0 Au0 u (здесь и далее запись x y, x, y R n означает, что для всех i = 1, n выполняются неравенства ( x)i ( y )i ). Тогда r ( A). При этом если n, n соответственно таковы, что n = max{ : u0 Anu0 }, n = min{ : Anu0 u0 }, то 1 1 n / n r ( A) n / n 1 и при этом последовательности { n / n } и { n / n } сходятся, соответственно монотонно возрастая и монотонно убывая, к r ( A).
На этом результате базируется следующий алгоритм построения монотонно сходящихся приближений к величине r ( A), который в подробной записи имеет следующий вид. Пусть n и n определяются формулами ( Anu0 )i ( A nu0 )i n = min ;
n = max. i =1, n i =1, n (u 0 ) i (u 0 ) i Замечание. Как следствие из работ Красносельского М.А., Стеценко В.Я. и др. [34], [36], [38], [39], [66], можно установить, что некоторые подпоследовательности этих последовательностей являются сходящимися, причем их предел равен r ( A). Тем самым построение этих последовательностей можно использовать для вычисления спектрального радиуса оператора A.
1 Далее запись n / n r ( A) означает факт монотонной сходимости УснизуФ 1 1 последовательности { n / n } к спектральному радиусу r ( A), а n / n r ( A) - факт 1 монотонной сходимости последовательности { n / n } УсверхуФ к числу r ( A).
С помощью разности 1/ n - 1/ n можно контролировать степень близости n n соответствующих последовательностей к величине r ( A). По предложенному в теореме 5.2 алгоритму автором была разработана соответствующая программа на языке программирования TURBO PASCAL. Пример 1. Пусть 0.1 0.2 A = 0.1 0.2 0. 0.1 0.3 0.1 0.6 0.1 0.1 0.2 0.1 0.6 0.3 0.3 0.1 0.2 0.1 0.2 0.2 0.5 0.3, 0.5 0. 1 1 u0 = 1. 1 Используя вышеизложенный алгоритм, найдем приближения (соответственно снизу и сверху) к спектральному радиусу матрицы A. Вычисления представим в виде таблицы.
Таблица 13 № п/п, n 1 2 3 4 8 16 32 1 n / n r ( A) 1 n / n r ( A) 0.800000 1.081665 1.134447 1.172925 1.228434 1.257382 1.272111 1. 2.000000 1.555634 1.466982 1.418077 1.351138 1.318685 1.302752 1. Как можно заметить из таблицы, на уже на 64-м шаге значение спектрального радиуса данной матрицы A заключено между 1.279540 и 1.294858. Точное значение спектрального радиуса данной матрицы равно 1.287012. Этот алгоритм в аналогичной форме приемлем для получения оценок снизу, соответственно сверху для спектрального радиуса интегрального оператора вида Ax ( t ) = K ( t, s ) x ( s ) ds (5.1) с неотрицательным непрерывным ядром K (t, s). В этом случае последовательности имеют вид n = min t K n ( t, s ) u 0 ( s ) ds u0 ( t ), n = max t K n ( t, s ) u0 ( s ) ds u0 ( t ), где K n (t, s ) - n -ое итерированное ядро, а u0 (t ) - непрерывная и положительная на функция. Отметим, что скорость сходимости последовательностей 1/ n и 1/ n к веn n личине спектрального радиуса r ( A) имеет порядок O. В связи с вышеизложенными результатами выясняется актуальность оценок спектрального радиуса r ( A) оператора A как в случае когда A - это 1 n квадратная (n n) матрица, так и в случае, когда A - интегральный оператор вида (5.1). Важную роль в теории для справедливости принципа Хикса в случае интегрального уравнения с неотрицательным ядром играет условие вида r ( A) < 1, (5.2) где r ( A) - спектральный радиус интегрального оператора A с ядром K (t, s). Естественно иметь признаки, обеспечивающие выполнение условия (5.2). Необходимо получить соответствующие признаки для случаев, когда A : 10) A = (aij ) (i, j = 1, n);
20) A - интегральный оператор вида (5.1), в котором - ограниченное замкнутое множество из евклидова пространства R m, K (t, s) - функция, для которой при некоторых p > 1 и q = p выполняется условие: p q q | K ( t, s)| ds dt < +. (5.3) При выполнении условия (5.3) оператор (5.1), как известно, действует в пространстве Lp () и является вполне непрерывным оператором в этом пространстве [66]. Соответствующие признаки для случая 10) были получены в работах Стеценко В.Я. Получим соответствующие признаки для случая 20). Предварительно напомним определение неразложимости оператора. Положительный линейный оператор A назовем неразложимым, если из того, что x >, x Ax ( > 0 ), следует, что x >>.
Введем в рассмотрение следующие функции P ( t ) = | K ( t, s)| ds, Q( t ) = | K ( s, t )| ds.
Теорема 5.3. Пусть для некоторого [0,1] выполняется следующее неравенство 38 P (t )Q1 (t ) 1, (t ) (5.4) и, кроме того, выполняется одно из двух следующих условий: 10) в неравенстве (5.4) равенство допускается лишь на множестве точек лебеговой меры нуль;
20) в неравенстве (5.4) строгое неравенство выполняется для всех t из некоторого множества, mes > 0, оператор A - неразложим в пространстве L p ( ). Тогда спектральный радиус r ( A) интегрального оператора A (5.1) в пространстве L p ( ) меньше чем единица:
r ( A) < 1.
Доказательство. Не ограничивая общности, можно считать, что K (t, s) 0, так как в противном случае мы бы перешли от оператора A к оператору A+ :
A+ x ( t ) = | K ( t, s)| x ( s) ds, для которого выполняются все условия теоремы и ядро которого неотрицательно. Если для этого оператора будет доказано утверждение теоремы, т.е. если доказано, что r ( A+ ) < 1, то учитывая неравенство r ( A) r ( A+ ) мы получим утверждение теоремы. Итак, оператор A положителен в L p ( ). Положим A = A.
Очевидно A, а, следовательно, и r ( A ) непрерывно по, а так как A0 = и r ( A0 ) = 0, то для всех достаточно малых > 0 выполнено неравенство r ( A ) < 1.
Возможны два случая: 1) r ( A1 ) < 1 ;
2) r ( A1 ) 1.
В первом случае теорема доказана, так как A1 = A. Во втором случае найдется хотя бы одно значение = 0 (0;
1], для которого r ( A ) = 1. В этом слу чае r ( A ) = 1 является собственным значением оператора A, которому отве0 чает неотрицательная собственная функция x0 ( t ) Lp ( ):
A0 x0 (t ) = x0 (t ), откуда в силу (5.4) K (t, s) x (s)ds P (t )Q1 (t ) x0 (t ), (5.5) где K ( t, s) = 0K ( t, s).
Установим, что в неравенстве (5.5) знак строгого неравенства имеет место на некотором множестве 1 : 1, mes1 > 0 для каждого из случаев 10), 20). При условии 10) это утверждение очевидно. При условии 20) утверждение следует из того, что неотрицательная собственная функция положительного неразложимого оператора в пространстве L p ( ), как квазивнутренний элемент конуса K неотрицательных функций пространства L p ( ), почти всюду в принимает положительные значения. Замечая, что 1 K 0 ( t, s) = K 0 ( t, s) K ( t, s) и применяя к левой части в (5.5) неравенство Гельдера с показателями p=, q= 1, получим p q q K 0 ( t, s) ds K 0 ( t, s) x0 ( s) ds x0 ( t ) P ( t ) Q1 ( t ) x0 ( t ). 1 Так как при этом K 0 ( t, s) K ( t, s), то K (t, s )ds q K (t, s ) x0 ( s )ds P (t )Q1 (t ) x0 (t ), (5.6) причем здесь строгое неравенство выполняется для всех t 1, где 1 и mes1 > 0.
Нетрудно видеть, что для всех t, для которых x0 (t ) > 0 выполняется также неравенство:
P(t ) > 0.
Действительно, если для некоторого множества 1, 1, P(t ) = (t 1 ), то в силу неотрицательности K (t, s) это означает, что для t 1, функция K (t, s ) как функция аргумента s на эквивалентна нулю для всех t 1. То гда эквивалентна нулю для всех t 1 на множестве и функция K (t, s) x0 ( s) и поэтому для t x0 ( t ) = 0 K ( t, s) x0 ( s) ds = 0, т.е. x0 (t ) 0 для t 1. Сказанное означает, что из неравенства (5.6) следует неравенство q K ( t, s) x0 ( s) ds Q1 ( t ) x0 ( t ), (5.7) причем в (5.7) знак строгого неравенства имеет место по крайней мере для t 1. Извлекая из обеих частей неравенства (5.7) корень степени (1 ), а за тем, интегрируя по t на множестве, получим dt K (t, s) x q q ( s )ds > Q(t ) x0 (t )dt.
Меняя в левой части порядок интегрирования, найдем что Q( t ) x q q ( t ) dt > Q( t ) x0 ( t ) dt.
Полученное противоречие доказывает невозможность неравенства r ( A1 ) 1.
Теорема доказана.
Аналогичный результат имеет место и в том случае, когда интегральный оператор Ax(t ) = K (t, s ) x( s )ds действует в пространстве С () и неразложим в этом пространстве относительно конуса неотрицательных функций пространства С (). з6. Построение приближений, сходящихся к собственному вектору линейного оператора Большое количество работ Крейна М.Г., Красносельского М.А., Стеценко В.Я. и др. посвящено проблеме отыскания собственных векторов как линейных, так и нелинейных операторов. В случае нелинейных операторных уравнений, проблема отыскания собственных векторов и собственных значений нелинейных операторов является существенно более сложной. В этом параграфе рассматривается задача на построение приближений к собственным значениям, собственным векторам, т.е. построение приближений к таким, x E, что x = F (x), (6.1) где F (x) - линейный или нелинейный оператор, действующий в банаховом пространстве E. По аналогии с предыдущим материалом будем считать, что пространство E полуупорядоченно с помощью конуса Крейна K [36]. Предположим, что оператор F (x) положительный, т.е для x K следует, что F ( x) K. При дополнительных предположениях относительно оператора F (x), уравнение (6.1) имеет для некоторого значения = 0 решение x0 = x* (0 ), принадлежащее K. Соответствующий вектор x0 естественно на звать собственным вектором оператора F (x), отвечающим собственному значению 0. Точное значение собственного вектора может быть найдено лишь в весьма частных случаях, поэтому возникает задача о построении приближений к собственному вектору, с заданной степенью точности. При этом особый интерес представляют методы позволяющие строить такие приближения un, vn к собственному вектору x*, которые удовлетворяют условию un x* vn и при этом x* un 0, x* vn 0. В этом случае, естественно, называть элементы un и vn как приближения к собственному вектору x* по недостатку и соответственно по избытку. Предложим соответствующие способы построения собственных векторов и собственных значений для некоторых классов линейных операторов. Рассмотрим вначале случай линейного положительного оператора. Его, в отличие от случая нелинейного оператора, привычнее обозначать не буквой F, а буквой A. Уравнение (6.1) в этом случае перепишется в виде x = Ax.
Элементы x, y K называются эквивалентными, если tx y и ty x при некотором t > 0. Конус K распадается на классы попарно эквивалентных элементов - компоненты эквивалентности. Для эквивалентных элементов x, y K определена величина inf {t : tx y}. sup{t : tx y} ( x, y ) = Оператор A будем предполагать не только положительным, но и фокусирующим. Напомним определение фокусирующего оператора [36]. Определение 6.1. Оператор A называется фокусирующим на конусе K, если он u0 -положительный и если для всех x >, y > существует постоянная 2, такая что ( Ax, Ay ) 2.
При этом число назовем постоянной фокусирования [38]. Приведем критерий фокусирования. Утверждение 6.1. Для того чтобы положительный оператор A был фокусирующим, необходимо и достаточно, чтобы существовали такие u0 K, const, что для каждого x K выполняется неравенство ( x)u0 Ax ( x)u0.
(6.2) Здесь u0 - фиксированный элемент конуса K. Это утверждение означает, что AK K u,.
Примерами фокусирующих операторов являются матрицы с положительными элементами. Лемма 6.1. Пусть x >, y > x ay, и y bx, (6.4) причем || x||u0 =|| y||u0 = 1. (6.5) Тогда функционал ( x, y ) = ln ( x, y ) обладает свойством:
x e ( x, y ) y, y e ( x. y ) x. (6.6) Заметим, что ( x, y ) является полуметрикой на множестве всех сравнимых между собой по конусу K элементов [36]. Теорема 6.1. Если A - фокусирующий оператор с постоянной фокусирования, тогда для всех x, y Ku [36]:
( Ax, Ay ) = 1 (x, y ), + т.е. в полуметрике ( x, y ) фокусирующий оператор является оператором сжатия на множестве Ku с постоянной q :
q 1 < 1. + (6.7) В случае, когда A - матрица с положительными элементами, постоянная фокусирования определяется следующей теоремой [38]. Теорема 6.2. Константа фокусирования относительно конуса K + R n линейного оператора А порожденного матрицей A с положительными элементами aij определяется равенством ( A, K+ ) = max i, j, p,q aip a jq a jp aiq.
Для всех x Ku определим оператор A :
44 Ax = Ax. || Ax ||u Оператор A рассмотрим на множестве E1 = Ku0 S1, где S1 = x: x Eu0,|| x||u0 = 1 }. Полуметрика ( x, y ), рассматриваемая на E1, является { метрикой. В самом деле, из равенства ( x, y ) = 0 ( x, y E1 ) следует, что x = y, > 0, но так как || x||u0 =|| y||u0 = 1, то = 1, т.е. x = y. Оператор A является на E1 оператором сжатия этого мет рического пространства, последний факт доказан в [38]. В силу сказанного A имеет в E1 единственную неподвижную точку x* :
Ax* = x* т.е.
Ax * =|| Ax * ||u0 x * и к x* сходится метод последовательных приближений xn +1 = Axn, (n = 0,1,2,...) при любом начальном приближении x0 Ku, x0. При этом на основании утверждения принципа сжатых отображений имеет место следующая оценка близости xn к x* :
qn ( x, xn ) ( x1, x0 ). 1 q * (6.8) y t2 x, то Здесь ( x, y ) определяется следующим образом. Пусть x t1 y, гда ( x, y ) = ln max(t1, t2 ). Тем самым установлена справедливость следующей теоремы.
Теорема 6.3. Пусть A - фокусирующий оператор с постоянной.Тогда A имеет в Ku0 собственный вектор x*, которому отвечает собственное значение 1. К этому вектору x* сходится метод xn + 1 = Axn || Axn ||u0 (n = 0,1,2,...) при любом x0 Ku, x0. При этом справедлива оценка близости (6.8), где q удовлетворяет неравенству (6.7). К собственному вектору x* также сходятся последовательности un и vn, которые удовлетворяют следующему неравенству un x* vn где a un = b b vn = a 1 1 2 + n An x0, (6.9) 1 1 2 + n An x0, (6.10) а постоянные a и b таковы, что ax0 Ax0 bx0.
Ясно, что коэффициенты в правой части (6.9) и (6.10) при n стремятся к единице. Как уже отмечалось в последней теореме последователь ность An x0 сходится к собственному вектору x*, в силу чего un и vn сходятся к x* по норме пространства Е. Итак, мы получили возможность строить последовательности un и vn, сходящиеся к x*, при этом un сходится по норме пространства E снизу, а vn сверху. Если теперь вместо оператора A взять сопряженный оператор A*, то учитывая, что этот оператор является положительным в E * относительно полугруппы K *, мы аналогичным образом получим способ построения приближений l1( n ), l2( n ), к собственному функционалу l * оператора A* :
( l1( n ) l * l2n ).
С помощью этих последовательностей мы на основании 0 r ( A) = l0 (v0 ) l0 (u0 ) можем утверждать, что l ( n ) (v ) l1( n ) (v0 ) r ( A) 0 + 2n ) 0, ( l1( (u0 ) l2n ) (u0 ) а это позволяет строить две последовательности, сходящиеся к r ( A), соответственно, снизу и сверху, тем самым с любой точностью находить значение спектрального радиуса r ( A) оператора A. Проиллюстрируем эти результаты соответствующими примерами. Пример 1. Пусть 1 3 A=, 2 1 1 u0 =, 1 1 x0 =. В данном примере точное значение собственного вектора, отвечающего ведущему собственному значению 1 : x * = 1. 0. Выберем в данном примере n=7. Используя метод, описанный в теореме 6.3 получим приближения к соответствующим координатам собственного вектора x*. Представим эти приближения в виде следующей таблицы. Таблица 14 № n п/п, Приближения к координатам вектора x* x1 x2 0.750000 0.846154 0.804348 0.821656 0.814338 0.817405 0. 1 2 3 4 5 6 1 1 1 1 1 1 Теперь, на основании теоремы 6.3, получим приближения к соответствующим координатам собственного вектора x* УснизуФ и УсверхуФ. В данном примере a=3, b=4, =2.449. Эти приближения также представим в виде таблицы.
Таблица 15 № п/п, n 1 un 0.91612 0.68709 0.96385 0.81557 0.98465 0.79200 0.99352 0.81633 0.99727 0.81212 0.99885 0.81647 0.99952 0.81572 vn 1.09156 0.81867 1.03750 0.87789 1.01559 0.81689 1.00652 0.82701 1.00274 0.81657 1.00115 0.81834 1.00048 0. Используя формулу (6.8), оценим в какой близости от точного решения x* на 7-м шаге мы находимся: ( x7, x* ) = 0.00114. В приведенном примере приближение x0 = (1;
1)T случайно оказалось достаточно близким от x* в метрике ( x, y ) :
( x0, x* ) = 0.49617.
Возьмем теперь начальное приближение x0 = (1;
4)T, сильнее отклоняющееся от x* :
( x0, x* ) = 3.72455.
В этом случае получим последовательно x1 = (1;
0.46)T, x2 = (0.97;
1)T x0.
Отметим, что для получения приближения с той же точностью, что и при выборе x0 = (1;
1)T нам понадобится в этом новом случае всего на две итерации больше, чем в предыдущем случае, т.е. пример говорит о том, что данный метод не очень УчувствителенФ к выбору начального приближения x0.
Пример 2. Пусть. 01 0.2 A = 01. 0.2 0.6 01. 0.3 01. 0.6 01. 01 0.3 0.2. 1 0.2 01 0.5. 1, u0 = 1, 01 0.2 0.3. 0.6 01 0.5. 1 0.3 0.2 0.4 1 1 2 x0 = 3. 4 В данном примере точное значение собственного вектора, отвечающего 0.483 0.693 ведущему собственному значению 1 : x * = 0.467. Возьмем 10 итераций, ис 1 0. пользуя метод, описанный в теореме 6.3, получим приближения к соответствующим координатам собственного вектора x*. Представим эти приближения в виде следующей таблицы. Таблица 16 № п/п, Приближения к координатам вектора x* n x1 1 2 3 4 5 6 7 8 9 10 0.487805 0.517167 0.476503 0.483112 0.483335 0.483425 0.483303 0.483326 0.483326 0. x2 0.560976 0.706009 0.695812 0.693664 0.692887 0.693335 0.693293 0.693289 0.693286 0. x3 0.414634 0.491416 0.464674 0.467055 0.466967 0.466967 0.466882 0.466892 0.466890 0. x4 1 1 1 1 1 1 1 1 1 x5 0.707317 0.841202 0.793159 0.785725 0.788263 0.788628 0.788491 0.788472 0.788480 0. Теперь, на основании теоремы 6.3, получим приближения к соответствующим координатам собственного вектора x* УснизуФ и УсверхуФ. В данном примере a = 0.56, таблицы.
b = 2.9, = 6. Эти приближения также представим в виде Таблица 17 № п/п, n un 1 0.02643 0.03039 0.02246 0.05418 0.03832 0.06445 0.08798 0.06124. 012462. 010483. 010766. 015721 010499. 0.22593. 017920. 016696 0.23972 016141. 0.34559 0.27154 0.22628 0.32439 0.21848 0.46816 0.36904 0.28112 0.40319 0.27155 0.58153 0. vn 9.00416 10.35478 7.65354 18.45853 13.05603 4.15009 5.66548 3.94345 8.02466 6.75035 2.10904 3.07972 2.05668 4.42608. 351058 1.39794 2.00720 1.35148 2.89362 2.27359 1.03240 1.48001 0.99681 2.13600 1.68373 0.83130. 119226 0.80300 1.71961 1. 50 7 0.32814 0.47071 0.31699 0.67895 0.53534 0.36654 0.52577 0.35408 0.75837 0.59796 0.39668 0.56900 0.38319 0.82073 0.64713 0.41972 0.60205 0.40544 0.86839 0.68471 0.71184 1.02113 0.68766 1.47287. 116134 0.63732 0.91418 0.61565 1.31861 1.03969 0.58890 0.84472 0.56887 1.21842 0.96070 0.55658 0.79836 0.53765. 115155 0. Ниже предлагаются два алгоритма построения собственных векторов x* и l * операторов A и A*, соответствующего значению 1.
Пусть A - неразложимый вполне непрерывный положительный оператор, u0 - фиксированный внутренний элемент K, n и n - последовательности такие, что n = inf { : Anu0 u0, u0 >> }, n = sup{ : Anu0 u0, u0 >> }.
Построим последовательности:
un = n u0 + n Au0 +... + An 2u0 + An 1u0, vn = n u0 + n Au0 +... + An 2u0 + An 1u0.
1 1 n 1 2 n 1 n n 1 1 n 1 2 n 1 n n Тогда согласно результатам [66] последовательности A un, Aun A vn Avn сходятся к единственному нормированному вектору оператора A, отвечающего собственному значению r ( A). Для отыскания l * проводятся аналогичные построения применительно к сопряженному оператору A*. Пусть A - линейный положительный оператор, действующий в банаховом пространстве E, полуупорядоченном конусом K, то есть AK K. Как известно [36,38,69] в этом случае оператор A, при некоторых дополнительных предположениях, имеет в K собственный вектор x*, отвечающий спектральному радиусу r ( A) оператора A :
Ax* = r ( A) x*.
Занумеруем собственные значения оператора A в порядке убывания их абсолютных величин, то есть r ( A) = 1 2... n. Тогда всякая точка спектра ( A) оператора A удовлетворяет неравенству r ( A) = 1, ( ( A) ).
Для различных классов положительных операторов (сильно положительные, u0 - положительные, фокусирующие, острые [36,38,69]) гарантировано строгое неравенство < r ( A) ( ( A), 1 ).
(6.11) Дополнительно предположим, что E = H - гильбертово пространство, A самосопряженный положительный оператор, то есть A* = A. Пусть y0 K, y0, l0 K *, l0. Положим 1 = l0 ( Ay0 ) l0 ( y0 ) и определим элементы l1 = y1 = 1 Ay0, l2 = y2 = 2 Ay1.
Вообще, пусть уже определены n 1, yn 1, ln 1. Положим n = ln 1 ( Ayn 1 ), ln 1 ( yn 1 ) ln = yn = n Ayn 1.
Для определенности последовательностей { n }, {yn }, {ln } необходимо и достаточно выполнения условия ln ( yn ) 0 для любого n. Для этого, например, достаточно, чтобы оператор A был неразложимым [36]. Наряду с последовательностью {yn } образуем последовательность xn = n = An y0 (n = 1,2,...).
Ясно, что для каждого n l1 = 1 x1 = 11, l2 = y2 = ( 2 1 )x2 = ( 2 1 ) 2,..., n n ln = yn = i xn = i n. i =1 i = Поэтому n = ln 1 ( Ayn 1 ) n 1 ( Axn 1 ) =. n 1 ( xn 1 ) ln 1 ( yn 1 ) Положим ( x n1) = xn xn = n n ( = n1), тогда, как легко видеть, имеет место неравенство n = ( ( n1)1 ( Axn1)1 ) ( ( n1)1 ( xn1)1 ) (n = 1,2,...).
(6.12) В силу (6.11) ( последовательности {xn1) } = { n(1) } сходятся к собственному вектору x* = * оператора A = A*, и поэтому в силу (6.12) последовательность { n } сходится к числу 1 = * ( Ax* ). * ( x* ) Аналогичным свойством сходимости к 1 обладает последовательность tn = l0 ( Ayn 1 ), l0 ( yn 1 ) n при этом разность tn 1 имеет порядок 2. Оказывается, что после 1 довательность { n } имеет более высокую скорость сходимости, а именно 2 n n 1 = 2. 1 Естественно теперь распространить этот метод на операторы, действующие в банаховом пространстве E с конусом K.
Исходя из y0 K, y0, l0 K *, l0, положим n = ln 1 ( Ayn 1 ), (n = 1,2,...) ln 1 ( yn 1 ) где ln = n A*ln 1, yn = n Ayn (n = 1,2,...).
Пусть x*,l * - собственные векторы операторов A, A*, соответственно, x* K, l * K * такие, что x * = l * =1. Тогда имеют место асимптотические оценки 2 n n 1 = 2, 1 yn yn x*, n ln l = 2. ln 1 * В отличие от самосопряженного оператора здесь, хотя объем работы возрастает в два раза, мы получаем приближения не только к собственному значению 1 и собственному вектору x* оператора A, но и к собственному вектору l * сопряженного оператора A*. По предложенным выше алгоритмам, автором были составлены программы на языке программирования TURBO PASCAL. Выше оператор A предполагался линейным. Построим приближения к собственному вектору x* для некоторых классов нелинейных операторов F (x). Выделим соответствующий класс нелинейных операторов F (x), дейст вующих в полуупорядоченном банаховом пространстве, являющимися монотонными относительно нормального конуса K и такими, что F (x) F ( x) для всех x K и [1;
+ ], где < 1, const. Если в полуупорядоченном банаховом пространстве E с конусом K ввести следующую метрику: для двух элементов x, y K таких, что x y, y x (6.13) положить d ( x, y ) = ln max{0, 0 }, где 0, 0, соответственно, точные нижние и верхние границы всех чисел, для которых выполняются неравенства (6.13), то, во-первых, d ( x, y ) удовлетворяет всем аксиомам метрики и во-вторых, для нормального конуса K всякая компонента связности Ck конуса K становится полным метрическим пространством в метрике d ( x, y ), а оператор F (x) является оператором сжатия соответствующей компоненты связности. При этом собственные векторы оператора F (x) из конуса K являются неподвижными точками оператора F ( x ), а каждая фундаментальная по метрике d ( x, y ) последовательность элементов {xn } является фундаментальной и по норме пространства E и наоборот. При этом пределы последовательностей {xn } по норме пространства E и по метрике d ( x, y ) совпадают.
Из этого в силу принципа Банаха сжатых отображений следует справедливость следующей теоремы. Теорема 6.4. Пусть конус K нормален и пусть для некоторых u0 > элементы u0 и F (u0 ) принадлежат одной составляющей конуса K. Тогда для всех, ( > 0 ) оператор F (x) имеет на составляющей Ck (u0 ) собственный вектор x* ( ), отвечающий собственному значению. Этот вектор может быть построен методом последовательных приближений xm +1 ( ) = F ( xm ( ) ) при любом начальном приближении x0 Ck (u0 ). При этом справедлива оценка близости d ( x * ( ), xm+ 1 ( )) m d ( x1 ( ), x0 ( )). 1 (6.14) Замечание. Неравенство (6.14) позволяет также получить оценку относительной погрешности для приближений xm +1 ( ), т.е. оценку величины || x * ( ) xm+1 ( )||, || x * ( )|| и позволяет утверждать, что в методе последовательных приближений наряду с абсолютной погрешностью, так же и относительная погрешность приближенного решения стремится к нулю. Последнее крайне важно, так как в линейных задачах на собственные векторы определяющим в оценке точности полученного приближения является именно оценка относительной погрешности полученного приближения.
ГЛАВА 3. НОВЫЕ АЛГОРИТМЫ И МЕТОДЫ ПОСТРОЕНИЯ ПРИБЛИЖЕНИЙ, СХОДЯЩИХСЯ К ТОЧНОМУ РЕШЕНИЮ ОПЕРАТОРНОГО УРАВНЕНИЯ ВИДА x = Ax + f з7. Об одном итерационном методе решения системы линейных алгебраических уравнений вида x = Ax + f с квадратной матрицей A, в случае, когда спектральный радиус матрицы A, больше чем единица В работе [69] был предложен метод решения уравнения вида x = Ax + f (7.1) с матрицей A, спектральный радиус которой больше единицы. Этот метод основан на переходе от уравнения вида (7.1) к уравнению y = By + g (7.2) с матрицей B, спектральный радиус которой меньше, чем спектральный радиус матрицы A (r ( B) < r ( A) ). Данный метод был реализован [69] для неотрицательных матриц A, спектральный радиус которых больше единицы. Однако этот метод обладает существенно большими потенциальными возможностями, в силу которых мы предлагаем прием решения уравнений вида (7.1) с матрицами A, необязательно являющихся неотрицательными матрицами. Данный прием основан на предварительном преобразовании уравнения (7.1) к новому уравнению вида (7.2), для которого, в случае r ( B) < выполнения определенных условий, будет выполнено неравенство: и, следовательно, для решения которого может быть использован метод последовательных приближений:
xm +1 = Bxm + f, (m = 0,1,...) при любом начальном приближении x0. Переходим к описанию этого метода. Занумеруем собственные значения матрицы A в порядке убывания их абсолютных величин, т.е. (A)=1|2|...|n|. Тогда всякая точка спектра (A) матрицы A удовлетворяет неравенству ||(A)=1 ((A)). Хорошо известно [34,36,38], что при некоторых дополнительных предположениях число = r ( A) является собственным значением матрицы A и собственным значением сопряженной матрицы, которой отвечают собственный вектор x* K матрицы A и собственный функционал l * K * матрицы A*, где K * - сопряженная к K полугруппа (т.е. совокупность всех линейных функционалов, принимающих на элементах конуса K неотрицательные значения):
Ax* = r ( A) x*, A*l * = r ( A)l *.
Способы отыскания этих собственных векторов приведены в Главе II. Собственные векторы матрицы A и A*, и собственное значение, необходимы нам для реализации преобразов55ания, уменьшающего спектральный радиус матрицы A, входящей в уравнение (7.1). Ниже предполагается, что A - вполне непрерывный оператор. Соответствующий метод основан на результатах работ В.Я Стеценко, Т.А. Костенко, В.А. Семилетова и заключается в следующем. Пусть у оператора A среди собственных значений только одно больше единицы, тогда: l * матрицы A и A*, 10) нормируем собственные векторы x* и соответственно условием l * ( x* ) = 1;
20) по матрице A строим матрицу B согласно формуле Bx = Ax 1l * ( x) x*, def где 1 = r ( A). При этом явный вид матрицы B может быть найден по виду матрицы A и виду векторов x* и l *. Спектр матрицы B расположен внутри круга с центром в начале координат и радиусом равным единице, что позволяет применять для решения уравнения с матрицей последовательных приближений. Как установлено в [69] наибольшее собственное значение матрицы B будет совпадать со вторым собственным значением 2 матрицы A, при этом 2 < 1 и, следовательно, спектральный радиус матрицы B будет меньше B метод спектрального радиуса матрицы A. Если при этом 2 < 1, то матрица B является оператором сжатия. В этом случае соответствующее уравнение (7.2) имеет и притом единственное решение и это решение можно получить по методу последовательных приближений ym +1 = Bym + g (m = 0,1,...) при этом мы можем найти это решение с любой наперед заданной точностью. Указанная схема позволяет решать уравнения с оператором A ((A)>1, |2|<1), если удастся установить связь между решениями xA и xB уравнений (7.1) и (7.2) соответственно. Для установления соответствующей связи предположим, что xA является решением уравнения (7.1), тогда, очевидно, в силу (7.3) имеем xA-BxA=f+1l*(xA)x* и в случае, если (B)<1, отсюда получаем xA=(I-B)-1[f+1l*(xA)x*], т.е.
x A = ( I B ) 1 f + 1 l ( x A ) ( I B ) 1 x = 14 4 23 ( I B )1 x, + = xB c так как, очевидно, что xB=(I-B)-1f - это решение уравнения x=Bx+f. Тем самым установлено, что xA=xB+c(I-B)-1x*. Введем обозначение (I-B)-1x*=yB. Ясно, что yB - решение уравнения y=By+x* и так как Bx*=, то yB=x*. Таким образом, установлено, что xA=xB+c x*.
(7.4) Итак, решение уравнения (7.1) можно представить в виде суммы решения xB уравнения (7.2) при g=f и собственного вектора x*. В случае если собственный вектор x* точно не известен, а известно некоторое приближение ~ к x*, то решение уравнения (7.1) можно представить в виде суммы x решения xB уравнения (7.2) при g=f и решения yB уравнения (7.2) при g= ~. x Это значит, что вместо того, чтобы решать уравнение с оператором A (напомним, что в общем случае (A) может быть больше 1), достаточно решить 2 раза уравнение (7.2) : один раз с правой частью f, второй раз с правой частью x*. Остается в этой схеме объяснить, как находить множитель c в формуле (7.4). Для этого достаточно подставить выражение (7.4) в уравнение (7.1), в результате чего мы получим уравнение с одной скалярной неизвестной c, что позволяет легко найти c. После этого c подставляем в (7.4) и в результате мы находим решение уравнения (7.1). В реальной ситуации нам не всегда бывают известны векторы x* и l*, однако, существуют методы, позволяющие найти приближения к этим ~ элементам. Предположим, что ~ и l достаточно близкие приближения к x* x и l* соответственно. Тогда оператор ~ ~ B x = Ax 1l ( x) ~ x ~ достаточно близок к оператору B и поэтому ( B ) ( B ), при этом не исключено, что ( B ) < 1.
~ В результате мы получили возможность использовать изложенную схему отыскания приближенного решения ~B x уравнения с оператором B, которое в силу сказанного будет достаточно близко к решению xB. Тем самым мы имеем возможность приближенного решения уравнения с оператором A в тех случаях, когда x* и l* точно неизвестны. Пример1. Рассмотрим систему линейных алгебраических уравнений вида (7.1), где 0.6 0.7 A= 0.7 0.6, 2 f =. 1 ~ Точное решение x* = 4.54545. 5.45454 x* Для отыскания собственных векторов изложенном в з6. В данном случае r ( A) = 1.3 x* = l * и l * матриц A и A*, соответствующего собственного значения 1 = r ( A) воспользуемся способом, () T 0.70711 = 0.70711. Заметим, что r ( A) = 1.3 > 1 поэтому решение уравнения (7.1) применения формулы (7.3) матрица B примет следующий вид:
0.05 0.05 B= 0.05 0.05, из которого следует, что r ( B) = 0.1 < 1. методом последовательных приближений не представляется возможным. В результате С помощью метода последовательных приближений решаем уравнение x = Bx + f. Этот метод сходится достаточно быстро, так как r ( B) = 0.1. В выберем x0 = f. Итерации метода Таблица качестве начального приближения x последовательных приближений представим в виде таблицы. Приближения xm (1.95000, 1.05000) (1.95500, 1.04500) (1.95450, 1.04550) (1.95455, 1.04545) (1.95454, 1.04545) (1.95454, 1.04545) Подставим x A x10 + c x* m 1 2 3 4 5 в (7.1), получаем 0.21213 1.95000 c 0.21213 = 1.95000, откуда c = 9.19239. Поэтому решение x A исходного уравнения:
4.5454 xA = 5.4545.
Как показывает практика, существуют примеры, в которых после однократного применения формулы (7.3) у полученной матрицы B спектральный радиус снова остается большим единицы. В случаях, когда среди собственных значений матрицы A есть значение меньше единицы, тогда к полученной матрице B следует повторно применить формулу (7.3), считая, что A = B, x* - собственный вектор полученной ранее матрицы B, l * собственный вектор матрицы B* ( B* -матрица сопряженная B ), а r (B) спектральный радиус матрицы B. Приведем пример соответствующий этому случаю. Пример 2. Рассмотрим систему (7.1), где 1 3 4 A = 2 3 1, 2 2 1 0.1667 Точное решение x = 0.3333. * 1 f = 1. Применяя способ, изложенный в з6 отыскания собственных векторов x* и l * матриц A и A*, а также собственного значения 1 = r ( A) матрицы A (при этом в качестве начального приближения взяты векторы l0 = (1,1,1)T и y0 = (1,1,1) ) находим, что в данном случае T 0.6794 0.4668 * r ( A) = 6.25, x = 0.5617, l = 0.7331. 0.4720 0.4944 * Применяя преобразование (7.3) к матрице A, получаем матрицу B1 :
0.9854 0.1180 1.8971 0.4221 0.7387 B1 = 0.3585 0.6207 0.1661 0.4609 у которой r ( B) = 1.9 > 1. Повторно применяя к матрице B1 преобразование (7.3) (при этом для отыскания собственных векторов x* и l * матриц B1 и B1*, ( B1* - матрица сопряженная B1 ) и спектрального радиуса матрицы B1 в качестве начального приближения взяты векторы l0 = (2,1,1)T и y0 = (1,1,2 )T ), получаем матрицу B2 :
0.0394 0.1641 0.5903 0.4365 0.3302, B2 = 0.0627 0.1661 0.1439 0.1672 у которой r ( B) = 0.6 < 1. С помощью метода последовательных приближений решаем уравнение x = B2 x + f. После 45 итераций получаем следующее приближение к решению уравнения x = B2 x + f :
1.5125 x45 = 1.1825. 1.2980 Далее, подставив * xB1 x45 + cB1 xB1, в уравнение x = B1 x + f находим cB, а затем соответственно x B1 - решение уравнения вида x = B1 x + f. Аналогично, подставив x A xB1 + c A x* A в уравнение (7.1), найдем 0.1667 x A = 0.3333. 0.0000 В действительности существуют и такие примеры, в которых даже после двукратного использования преобразования (7.3) получаем некоторую матрицу, спектральный радиус которой все еще больше единицы. Продолжая применять преобразование (7.3) к только что полученной матрице мы можем рассчитывать получить такую матрицу, спектральный радиус которой меньше единицы (это возможно только в случаях, если среди собственных значений исходной матрицы исходной матрицы A есть значение меньше единицы), что позволяет применить к ней метод последовательных приближений для отыскания решения уравнения вида x = Bs x + f, где s общее количество полученных матриц B.
Связь между решениями уравнений вида x = Bs 1 x + f и x = Bs x + f формулой:
можно установить следующей * x Bs1 = x n ( B s ) + cBs1 x Bs, (7.6) где Bs - последняя полученная матрица, для которой r ( Bs ) < 1, n - число итераций для уравнения вида x = Bs x + f, cBs 1 - скалярный множитель, * xBs - собственный вектор матрицы Bs 1, отвечающий r ( Bs 1 ), xn ( Bs ) - вектор решения уравнения вида x = Bs x + f, xBs - вектор решения уравнения вида x = Bs 1 x + f.
При этом A = B0. Пример 3. Рассмотрим систему вида (7.1), где 1 2 A= 4 3 1 1 2 1 2 3 3 1 3 1, 2 1 1 1 f =. 1 Применяя способ, изложенный в з6, отыскания собственных векторов x* и l * матриц A и A*, а также спектрального радиуса матрицы A (при этом в качестве начального приближения взяты векторы l0 = (2,1,1,1)T и находим:
0.4229 0.6156 0.4741 0.3168 r ( A) = 7.87, x* =, l* =. 0.6866 0.5446 0.3534 0.4732 y0 = (1,2,1,1)T ), Используя преобразование (7.3) к матрице A, получаем матрицу B1 :
1.4239 1.0503 0.0553 0.1859 0.7666 0.2983 0.1829 0.9666 B1 =, 0.6715 0.2869 0.0551 0.5585 1.2867 0.1182 0.5158 0.3170 у которой r ( B) = 2.3 > 1.
Повторно применяя к матрице B1 преобразование (7.3) (при этом для отыскания собственных векторов x* и l * матриц B1 и B1*, ( B1* - матрица сопряженная B1 ) и спектрального радиуса матрицы B1 в качестве начального приближения взяты векторы l0 = (1,2,1,1)T и y0 = (1,1,2,1)T ), получаем матрицу B2 :
2.4086 2.3265 0.1969 0.5630 0.3980 0.1940 0.9960 0.6897 B2 =, 1.2944 0.3560 0.1290 1.0391 2.2968 0.2302 0.8143 1.0963 у которой r ( B2 ) все еще больше единицы. В случаях многократного использования формулы (7.3) при реализации предложенного метода, можно установить общую связь между матрицами Bs 1 и Bs, считая что A = B0 :
* * B s x = B s 1 x r ( B s 1 ) lB * ( x ) x B s s (7.7) Повторно применяя к матрице B2 теперь уже преобразование (7.7) (при * этом для отыскания собственных векторов x* и l * матриц B2 и B2, * ( B2 матрица сопряженная B2 ) и спектрального радиуса матрицы B2 в качестве начального приближения взяты векторы l0 = (1,1,1,2)T и y0 = (2,1,1,1)T ), получаем матрицу B3 :
0.0847 0.1892 0.4509 0.2148 0.1994 0.1720 0.9373 0.8426 B3 =, 0.0540 0.2186 0.2382 0.0836 0.2854 0.0074 0.2189 0.4532 у которой r ( B3 ) = 0.81 < 1. С помощью метода последовательных приближений решаем уравнение x = B3 x + f.
После 30 итераций получаем следующее приближение к решению уравнения x = B3 x + f :
65 2.5381 0.7879 x30 (B3 ) =. 0.9645 2.7556 Далее используя формулу (7.6), получаем решение исходного уравнения (7.1) :
0.9983 2.4958 xA =. 1.4983 1.4974 Возможности применения этого метода достаточно значительны, о чем в частности свидетельствуют рассмотренные выше примеры. з8. Получение двусторонних оценок точного решения x* операторного уравнения вида x = Ax + f, в случае, когда спектральный радиус не обязательно меньше единицы. В данном параграфе предлагается метод получения оценок вида u x* v, (8.1) где x* - решение линейного операторного уравнения второго рода x = Ax + f, (8.2) где A - линейный оператор, действующий в пространстве E, f - заданный элемент пространства E. Пространство E предполагается полуупорядоченным при помощи конуса K, неотрицательных элементов.
При этом в параграфе используются понятия и терминология банаховых пространств, полуупорядоченных с помощью конуса Крейна K (K E ). Наличие оценок вида (8.1), которые естественно назвать двусторонними оценками решения, представляется достаточно важным и информативным. В самом деле оценка вида (8.1) позволяет утверждать, что нам известны приближения un к решению x* уравнения (8.2) по недостатку, а также приближения vn к x* по избытку, при этом элементы x* un, и vn x* представляются как оценки (векторные) для решения x*. Если конус K обладает свойством нормальности, то величина погрешности, с которой мы знаем эти приближения к решению x*, характеризуется нормой разности, которое не превосходит величины v u :
vu.
Отсюда следует важность получения оценок u, v решения x*. Отметим, что для отыскания приближений un, vn, известны разные методы [36]. В данном параграфе предлагаются новые подходы к получению таких оценок u, v неизвестного решения x* уравнения (8.2). Соответствующие оценки базируются на следующих теоремах [66]: Теорема 8.1. Пусть xn p, xn, xn + p (n = 0,1,2,...) соответствующие приближения к решению x* метода последовательных приближений xm +1 = Axm + f.
(m = 0,1,2,...).
(8.3) Подчеркнем, что при этом сходимость этих последовательных приближений к x* заранее не предполагается. Пусть постоянная такова, что [0;
1) и при этом выполнено неравенство xn + p xn (xn xn p ).
(8.4) Тогда для решения x* уравнения (8.2) (если это решение существует) справедлива следующая оценка x * xn + p + ( xn + p xn ), которую естественно назвать априорной оценкой УсверхуФ неизвестного решения x*. Теорема 8.2. Пусть xn p, xn, xn + p (n = 0,1,2,...) соответствующие приближения к решению x* метода последовательных приближений (8.3). Пусть постоянная неравенство такова, что < 1 и при этом выполняется (xn xn p ) xn + p xn, (8.5) тогда справедлива следующая априорная оценка УснизуФ для неизвестного решения x* :
x * xn + p + ( xn + p xn ).
Важно подчеркнуть, что приведенные оценки УснизуФ и УсверхуФ являются на самом деле достаточно точными даже в тех случаях, когда приближения xn p, xn, xn + p (n = 0,1,2,...) достаточно далеки от точного решения x*. Удивительным является и тот факт, что оценки УснизуФ и УсверхуФ для x* могут сходиться к решению даже в том случае, когда метод последовательных приближений (8.3) вообще не сходится (последнее заведомо будет иметь место в случае когда спектральный радиус оператора A больше чем единица). Предложенные ниже примеры иллюстрируют такую ситуацию. Приведем примеры применения вышеизложенного метода получения двусторонних оценок. Пример 1. Рассмотрим уравнение вида (8.2), где 0.1 0.12 A = 0.15 0.1 0. 0.15 0.14 0.11 0.1 0. 0.13 0.14 0.13 0.11 0.12 0.1 0.13 0.13 0.17 0. 0.1 0.14 0.12, 0.12 0. 1 2 f = 3. 4 Точное решение данного уравнения 5.85367655 7.04617563 x* = 7.64556639, а спектральный 8.61739842 10.11023145 радиус r ( A) = 0.6199.
1 1 В качестве начального приближения выберем вектор x0 = 1. Выбрав в 1 данном примере n = 4, p = 2, получим:
3.2332000 4.3282000 x2 = 5.1026000 6.1686000 7.3192000 4.8478793 6.0010283 x4 = 6.6679146, 7.6764155 9.0362385 5.4670630 6.6444378 x6 = 7.2697728. 8.2557006 9.6974076 Используя (8.4), (8.5), получаем и :
= 0.38506, = 0.38347.
Тогда точное решение x* исходного уравнения заключено между следующими границами:
5.85479 5.85219 7.04733 7.04463 7.64412 x* 7.64665. 8.61844 8.61601 10.11142 10.10865 Итак, здесь точность вычислений составляет 102. Пример 2. Рассмотрим уравнение вида (8.2), где.. 0.2 011 013 0.31. 0.37 0.241 0.33 01, A= 0.34 0.32 0.3 0.2. 0.2 0.31 01 0.24 1 1 f =. 1 Точное решение данного уравнения 12.80737245 * 18.32392049, а спектральный x= 20.26207124 14. радиус r ( A) = 0.9388.
69 1 1 В качестве начального приближения выберем вектор x0 =. В данном 1 примере выбрав n = 4, p = 1, получим:
3.0636876 3.9727109, x3 = 4.3060713 3.3881505 3.6598517 4.8508063, x4 = 5.2823728 4.0880412 4.2195602 5.6751766. x5 = 61989277. 4. Найдем и используя (8.4), (8.5) :
= 0.93885, = 0.93878.
Тогда точное решение x* исходного уравнения заключено между следующими границами:
12.81289 12.80306 18.31743 x * 18.33192. 20.27100 20.25490 14.83287 14. Любопытно отметить, что оценку для решения мы получаем и в том случае, когда спектральный радиус оператора A больше единицы (r ( A) > 1), т.е. в случае когда метод последовательных приближений заведомо расходится. Приведем соответствующий этому случаю пример. Пример 3. Рассмотрим уравнение вида (8.2), где 0.43 0.5 A= 0.44 0.2 011 0.232. 0.41 0.52 0.31 0.33 0.3 01. 0.4 01., 0.4422 0.51 1 1 f =. 1 Точное решение данного уравнения 2.8541858 * 3.9317454, а спектральный x= 4.9413177 2. радиус r ( A) = 1.2923.
70 1 1 В качестве начального приближения выберем вектор x0 =. Выбрав 1 1 n = 5, p = 2, получим:. 55789683 11.2320483 20.6730281.. 6.5091982, x = 135079548, x = 251967418. x3 = 7.7995472 5 16.3381634 7 30.6004789 5.3022657 10.6108577 19. Используя (8.4), (8.5) получим и :
= 1.67046, = 1.67006.
Тогда точное решение x* исходного уравнения заключено между следующими границами:
2.84934 2.85772 3.93645 x * 3.92608. 4.93433 4.94699 2.61559 2. Важно также подчеркнуть, что приближения xn p, xn, xn + p (n = 0,1,2,...) могут быть получены не только по методу последовательных приближений, но и по методу однопараметрического итеративного агрегирования [72]. В данном случае получим два вектора, находящиеся в определенной степени близости от точного решения x*, причем точность полученных таким способом векторов будет выше, чем точность соответствующих приближений, полученных по методу однопараметрического итеративного агрегирования. Отметим также, что хотя при помощи этих векторов нельзя будет оценить точное решение x* снизу и сверху, тем не менее, их степень точности будет намного выше, чем у соответствующих оценок точного решения x*. Приведем соответствующий пример. Пример 4. Рассмотрим уравнение вида (8.2), где 71 0.43 0.5 A= 0.44 0.2 011 0.232. 0.41 0.52 0.31 0.33 0.3 01. 0.4 01., 0.4422 0.51 1 1 f =. 1 Точное решение данного уравнения 2.8541858 * 3.9317454, а спектральный x= 4.9413177 2. радиус r ( A) = 1.2923.
1 1 В качестве начального приближения выберем вектор x0 =. Выбрав 1 1 n = 5, p = 2, получим: 2.8475888 2.8533233 2.8542158. 38955860, x = 3.9328087, x = 3.9318695. x3 = 5 4.8900915 4.9414894 7 4.9415040 2.5896551 2.6192712 2. Используя (8.4), (8.5) получим и :
= 0.15564, = 0.02523.
Тогда точное решение x* исходного уравнения можно оценить при 2.85419 3.93189 помощи векторов 4.94150 2.62011 2.85438 3.93169 и, при этом не обязательно точное 4.94150 2.62029 решение x* заключено между этими векторами. Как видно из этого примера, по сравнению с предыдущим, заметно повысилась точность оценки решения. В данном случае точность составляет 10-3. Пример 5. Рассмотрим уравнение вида (8.2), где 0.8 0.3 0.2 0.78 A = 0.29 015.. 017 0.2 0.3 0.23 014. 019 0.2 0.21. 0.63 01 015,.. 01 0.4 012.. 0.28 0.29 0.71 0.23 0.2 1 1 f = 1. 1 Точное решение данного уравнения 2.49235353 2.18734811 x * = 1.43998764, а спектральный 0.57455446 2. радиус r ( A) = 1.5031.
1 1 В качестве начального приближения выберем вектор x0 = 1. Выбрав 1 1 n = 6, p = 2, получим: 2.4869409 2.4905301 2.4918539 2.1972947 2.1901038 2.1882051 x4 = 1.4535331, x6 = 1.4412772, x8 = 1.4398975. 0.5889179 0.5762146 0.5748209 2.8323441 2.8303238 2. Используя (8.4), (8.5) получим и :
= 0.36883, = 0.10972.
Тогда точное решение x* исходного уравнения можно оценить при 2.49201 2.18797 помощи векторов 1.43972 0.57464 2.82965 2.49262 2.18709 и 1.43909, при этом не обязательно точное 0.57400 2.82938 решение x* заключено между этими векторами. Приведенные примеры подтверждают, что применение метода однопараметрического итеративного агрегирования фактически способствует увеличению точности получаемых оценок решения уравнения.
По предложенному в этом параграфе методу автором составлена программа на языке программирования TURBO PASCAL.
з9. О некоторых подходах к уточнению границ решения операторных уравнений вида x = Ax + f в случае, когда спектральный радиус r ( A) не обязательно меньше единицы. В данном параграфе предлагается способ уточнения оценок вида (8.1). Приведенные оценки могут быть уточнены, если известно, что оператор A p обладает дополнительными свойствами, например, если этот оператор u0 -ограничен снизу [66].
Оператор Ap называется u0 -ограниченным x > снизу, где u0 > фиксированный элемент, если для каждого = ( x) > 0, что выполняется неравенство A p x ( x)u0.
существует такое В частности A p u0 0u ( 0 > 0).
(9.1) Возможность улучшения полученных оценок для u0 - ограниченных снизу операторов основана на том, что для таких операторов из неравенства xn + p xn (xn xn p ), (9.2) где xn + p, xn, xn p - приближения к точному решению x*, полученные по методу последовательных приближений ( n и p - фиксированные натуральные числа (n p ) ), причем (последнее 0 < 1, вытекает более сильное, чем неравенство xn + sp xn + ( s 1) p s 1 ( xn + p xn ), справедливо для любого натурального s 2, благодаря положительности, а потому и монотонности линейного оператора A), неравенство вида ( xn + sp xn + ( s 1) p s 1 ( xn + p xn ) ns,)p, ( где ns,)p.
Справедлива следующая теорема [66]. Теорема 9.1. Пусть оператор A p является u0 - ограниченным снизу. Пусть выполнено неравенство (9.2) и > 0. Тогда имеет место следующее уточнение оценки УсверхуФ для решения x* уравнения (8.2) :
x * xn + p + ( xn + p xn ) (1 )(1 0 ) u0, где и 0 определяются согласно (9.2) и (9.1), а = [ (xn xn p ) (xn + p xn )] > 0.
Теорема 9.2. Пусть оператор A p является u0 - ограниченным снизу. Пусть для последовательных приближений (xn xn p ) xn + p xn, xn + p, xn, xn p, где n и p фиксированные натуральные числа (n p ), выполняется неравенство (9.3) причем 0 < 1 и > 0. Тогда имеет место следующее уточнение оценки УснизуФ для решения x* уравнения (8.2) :
x * xn + p + ( xn + p xn ) + (1 )(1 0 ) u0, где и 0 определяются в соответствии с неравенствами (9.3) и (9.1), а 1 = 1 [(xn + p xn ) (xn xn p )] > 0.
Ниже будут рассмотрены примеры, в которых реализовывается метод получения оценок точного решения x* операторного уравнения вида (8.2) и способ улучшения этих оценок. Также рассматривается вариант предложенного метода в УсвязкеФ с методом однопараметрического итеративного агрегирования. К полученным таким методом оценкам точного решения x* операторного уравнения вида (8.2) улучшения этих оценок. применяется способ Пример 1. Рассмотрим уравнение вида (8.2), где 01 0.31.. 0.05 012. 0.06 0.27 0.29 013, A= 0.41 0.053 011 0.21.. 017 0.04 0.36 0.22 1 2 f =. 3 4 r ( A) = 0.727.
В данном примере спектральный радиус В качестве начального приближения выберем вектор 1 1 x0 =. 1 Точное решение 7.135319126 * 9.39508034. Зафиксируем n = 5, p = 2, получим: x= 9.99663311 11.77896844 4.338243. 5822515, x3 = 6.583639. 8110907 5.650142 6.350149 7.505754, x = 8.396079. x5 = 7 8189273 9.041989. 9.849658 10. Здесь = 0.53358, = 0.52302. Тогда вектор решения x* данного уравнения заключен между следующими векторами:
7.11771 7.15096 9.37233 x * 9.41461. 9.97700 10.01750 11.75622 11. Как видно точность полученных оценок составляет 10-1. Теперь применим к полученным результатам способ улучшения оценок, который был описан 1 1 выше. Выберем в качестве u0 =. Тогда оценки точного решения x* примут 1 следующий вид:
76 7.13307 7.13826 9.38769 x * 9.40192. 9.99236 10.00481 11.77158 11. Точность у полученных оценок возросла и составляет 10-2. Воспользуемся теперь для этого же примера синтезом метода получения оценок точного решения приближения x* операторного уравнения вида (8.2) и метода однопараметрического итеративного агрегирования. В данном случае xn + p, xn, xn p получены по методу однопараметрического итеративного агрегирования. Здесь также n = 5, p = 2. Получим соответствующие приближения:
7.13136 7.13723 3.34939, x = 9.39738, x3 = 5 9.97545 9.99566 11.70409 11.78115 7.13526 9.39514. x7 = 9.99668 11. Здесь = 0.05071, = 0.33579. Тогда точное решение x* можно оценить при помощи следующих векторов:
7.13576 7.13516 9.39570 и 9.39502. 9.99642 9.99674 11.77961 11. Как видно по сравнению с предыдущими оценками здесь заметно возросла точность и теперь она составляет 10-3. В данном случае модификация предложенного метода намного улучшает оценки точного решения x* операторного уравнения вида (8.2). Рассмотрим теперь пример с таким линейным оператором A, у которого спектральный радиус r ( A) > 1. Пример 2. Рассмотрим уравнение вида (8.2), где 77 0.45 0.06 A= 0.41. 017 0.31 0.27 0.29 013., 0.53 011 0.21. 0.47 0.36 0.22 012. 01. 1 2 f =. 3 4 r ( A) = 1.015.
В данном примере спектральный радиус В качестве начального приближения выберем вектор 1 1 x0 =. 1 Точное решение 158.9741086 114.8110005 * x =. Зафиксируем n=8, p=2, тогда получим: 181.2641594 182.3613668 14.52504 19.91487 12.31833, x = 16.26772, x6 = 8 18.73744 24.95073 20.35843 26.65614 25.47222 20.33980. x10 = 31.35698. Отметим тот факт, что в данном случае приближения, полученные по методу последовательных приближений не сходятся к решению уравнения вида (8.2), т.к. r ( A) > 1. Тем не мене получим следующие оценки точного решения x*, где = 1.03108, = 1.03106 :
159.02434 158.89897 114.84789 x * 114.75602. 181.32226 18117774. 182.42023 182. Итак, несмотря на то, что метод последовательных приближений в данном случае фактически УрасходитсяФ, полученные оценки достаточно близки от точного решения x*. Воспользуемся теперь модификацией метода получения оценок точного решения x* операторного уравнения вида (8.2) и метода однопараметрического итеративного агрегирования. Здесь также n=8, p=2, 1 1 x0 =. Получим соответствующие приближения: 1 1 159.01063 114.84337, x6 = 181.30776 182.41119 158.97515 114.81199, x8 = 181.26545 182.36289 158.97413 114.81103. x10 = 181.26419 182. Здесь = 0.03086, = 0.02873. Тогда точное решение x* можно оценить при помощи следующих векторов:
158.974106 158.974214 114.811001 и 114.811110. 181.264158 181.264266 182.361368 182. В данном случае заметно возросла точность и теперь она составляет 10-3. Применение в данном случае модификации предложенного метода намного улучшает оценки точного решения x* операторного уравнения вида (8.2). Но применение здесь способа улучшения оценок не увеличивает точность полученных оценок. Напомним еще раз, что в данном случае r ( A) > 1. Итак, применять способ улучшения полученных оценок точного решения x*, возможно только в том случае, если спектральный радиус оператора A меньше единицы r ( A) < 1. Если до этого мы рассматривали примеры, у которых линейный оператор A - матрица, у которой все элементы были положительными, то теперь рассмотрим такие примеры, у которых матрица A, таким свойством не обладает. Пример 3. Пусть дано уравнение вида (8.2), где. 0.05 012 0.47 0.31 013. 0.06 0.27 0.29 A=, 0.41 0.053 011 0.21.. 017 0.04 0.36 0.22 1 2 f =. 3 В данном примере спектральный радиус r ( A) = 0.7604. В качестве 1 1 x0 =. 1 начального приближения выберем вектор Точное решение 0.7990584 4.5837095 * x =. Зафиксировав n=8, p=2, тогда получим: 3.1281162 3.7453674 0.88105 4.59444 x6 =, 3.20047 3.67094 0.84543 0.825725 4.59210 4.588753 x8 =, x10 =. 3.17126 3.153246 3.70245 3.720579 Здесь = 1.43655, = 0.55320. Тогда координаты вектора точного решения x* можно оценить при помощи следующих векторов: 0.80133 4.58460 3.13094 3.74302 0.89057 4.59979 и. 3.21254 3.66093 Как видно в этом случае точное решение x* нельзя оценить УснизуФ и УсверхуФ, при помощи полученных векторов, как, например, это было в случае, когда линейный оператор элементами. Попробуем применить способ улучшения оценок в данном случае.
1 1 Выберем в качестве u0 =. Тогда для оценки точного решения x* получим 1 1 A - матрица с положительными следующие векторы:
0.80018 0.85749 4.58345 4.56671 3.12979 и 3.17946. 3.74187 3.62786 Принципиально ситуация не изменилась.
А теперь применим к рассматриваемому примеру модификацию методов получения оценки точного решения x* и однопараметрического итеративного 1 1 x0 =, n=8, 1 агрегирования. Здесь также p=2. Получим следующие приближения:
1.00624 4.60087 x6 =, 3.31259 3.55834 0.91708 0.86711 4.59250 4.58861 x8 =, x10 =. 3.23603 3.19080 3.63808 3.68338 Здесь = 0.59085, = 0.46347. Тогда точное решение можно оценить при помощи следующих векторов:
0.82395 0.79495 4.58526 4.58301 3.15172 и 3.12547. 3.72251 3.74880 Итак, в случае, когда матрица A ( r ( A) < 1 ) не является положительной, нельзя получить оценки снизуФ и УсверхуФ точного решения x* и, соответственно получить уточнение полученных оценок. Если в предыдущем примере r ( A) < 1, то теперь рассмотрим пример в котором r ( A) > 1. Пример 4. Пусть дано уравнение вида (8.2), где. 0.05 012 0.47 0.31 013. 0.6 0.27 0.59 A=, 0.69 0.53 0.71 0.21 0.27 0.04 0.36 0.22 1 2 f =. 3 В данном примере спектральный радиус r ( A) = 1.26617. В качестве 1 1 x0 =. 1 начального приближения выберем вектор Точное решение 7.523184 * 4.206156. Зафиксировав n=16, p=1, получим: x= 8.446543. 11846489 155.75808 87.24385, x15 = 332.23149 144.35238 199.21668 109.35176, x16 = 422.91068 185.92579 254.24363 137.34191. x17 = 537.72694 238. Как видно, приближения, полученные по методу последовательных приближений, УудаляютсяФ от точного решения x*. Тем не менее, точное решение x* можно оценить при помощи следующих векторов:
7.59769 7.49774 4.15304 и 4.20389. 8.61703 8.40846. 11.91803 Отметим, что полученные оценки обладают достаточно высокой точностью. Применение к полученным векторам способа улучшения оценок не дает ожидаемого эффекта. Из проделанных вычислений следует, что использование в данном случае модификации точности. Рассмотрим теперь пример с таким оператором A, спектральный радиус которого намного больше единицы. Пример 5. Пусть дано уравнение вида (8.2), где методов получения оценки точного решения x* и однопараметрического итеративного агрегирования не дает выигрыша в 82. 1 0.95 012 0.97 0.31 0.6 0.89 0.59 0.93, f = 2. A= 3 0.99 0.38 0.71 0.21 4 0.2 0.84 0.03 0. В данном примере спектральный радиус r ( A) = 2.0022. В качестве 1 1 начального приближения выберем вектор x0 =. Заметим, что в данном 1 1 2.189895 * 5.620456. Зафиксируем n=4, p=1. Для оценки примере точное решение x = 2.652581 2. точного решения x*, получим соответствующие приближения:
10.51584 17.69660 27.78023. 25.31423, x = 5016418, x = 95.00877. x3 = 4 5 17.47908 30.55574 52.02921 23.25953 44.03518 82. Здесь = 1.83672, = 1.40426. Тогда точное решение заключено между следующими векторами:
7.24697 5.64526 60.76652 x * 3.43134. 22.56253 4.89195. 50.35785 Как видно, полученные оценки очень далеки от точного решения x*, тем не менее, они позволяют получить УнижнююФ и УверхнююФ границы точного решения x* операторного уравнения вида (8.2). Использование в данном случае способа улучшения полученных оценок ситуацию не изменяет. Ситуация не изменяется и при применении модификации методов получения оценки точного решения x* и однопараметрического итеративного агрегирования.
Итак, из рассмотренных выше примеров можно сделать вывод, что предложенный выше способ и метод в [59] и их модификации обладают большим потенциалом. Оценку v решения x* назовем активной оценкой решения уравнения вида (8.2) сверху, если Av + f v.
Аналогично, оценку u решения x* назовем активной оценкой решения уравнения вида (8.2) снизу, если Au + f u.
Очевидно, что наличие активных оценок сверху и снизу решения x* позволяет их улучшать. Именно, если un = Aun 1 + f, vn = Avn 1 + f (n = 1,2,...;
u0 = u, v0 = v), где u0,v0 - активные оценки, то un, vn при всех n также являются активными оценками. При этом, если r ( A) < 1, то un, vn сходятся к решению x*, причем для всех значений n un x* vn, то есть мы имеем сходящиеся к решению x* двусторонние приближения. Понятно, что это свойство активных оценок представляет значительный интерес, а получение таких оценок представляется весьма актуальным. В этой связи интересно исследовать полученные выше оценки на предмет наличия у них свойства активности. Однако прежде сделаем следующее замечание. Очевидно, всякое решение x* уравнения (8.2) является для любого натурального s также решением уравнения x = As x + f1, (9.4) где f1 = As 1 f + As 2 f +... + Af + f, (9.5) то есть уравнения x = A1 x + f при A1 = As. Оператор As, очевидно, линеен и положителен одновременно с оператором A. Теорема 9.3. Все оценки, полученные в теоремах 8.1, 8.2, 9.1, 9.2, являются активными. Доказательство. Ограничимся доказательством Итак, пусть выполнены условия теоремы 8.2. Пусть в (9.4) и (9.5) s = p и A1 = A p. Тогда, очевидно, для элемента u1 = xn + p + активности оценки снизу теоремы 8.2 (для остальных оценок доказательства аналогичны).
( xn + p xn ) достаточно доказать, что A1u1 + f1 u1.
Последнее неравенство эквивалентно неравенству ( xn + 2 p xn + p ) + ( xn + 2 p xn + p ) ( xn + p xn ), а это неравенство, в свою очередь, эквивалентность неравенству 1 ( xn + 2 p xn + p ) ( xn + p xn ). 1 Справедливость последнего неравенства следует из условия теоремы 8.2 и монотонности оператора A1 Теорема доказана. Наличие активных оценок снизу и сверху решения x* позволяет использовать более эффективный прием их улучшения, чем итеративные методы улучшения, изложенный выше. Этот прием приводит к новым активным оценкам решения. Опишем этот прием на примере его применения к оценкам в теоремах 8.1, 8.2, полагая, для простоты записи и выкладок, что в последних p = 1. Теорема 9.4. Пусть числа и удовлетворяют, соответственно, неравенствам (8.4) и (8.4), а число m1 неравенству 85 1 [( xn +1 xn ) ( xn xn 1 )] m1 1 [ ( xn xn 1 ) ( xn +1 xn )]. 1 1 (9.6) Тогда для решения x* уравнения (8.2) верна следующая оценка снизу:
x* 1 ( xn +1 xn ) + m1 xn +1 + ( xn +1 xn ). xn +1 + 1 + m1 1 1 (9.7) Аналогично, если m2 удовлетворяет неравенству 1 [ ( xn xn 1 ) ( xn +1 xn )] m2 [( xn +1 xn ) ( xn xn 1 )] 1 1 (9.8) то x* 1 ( xn +1 xn ) + m2 xn +1 + ( xn +1 xn ). xn +1 + 1 + m2 1 1 (9.9) Остановимся на доказательстве оценки (9.7). Условие (9.6), как нетрудно проверить, означает справедливость следующего неравенства ( Au0 + f ) u0 m1 [v0 ( Av0 + f )], где u0 и v0, соответственно выражаются формулами u 0 = xn + v0 = xn + ( xn xn 1 ), ( xn xn 1 ).
Тогда из результатов работы [64] следует справедливость оценки (9.7). Аналогично, условие (9.8) означает, что v0 ( Av0 + f ) m2 [( Au0 + f ) u0 ], из которого опять на основании [64] вытекает оценка (9.9). Оценки (9.7) и (9.9) заведомо лучше оценок в теоремах 8.1, 8.2, соответственно, если m1 > 0 и m2 > 0. Последнее условие выполняется, если конус K телесен, а оператор A переводит ненулевые элементы конуса K во внутренние элементы K. В случае A = (aij ), E = R n при конусе K векторов с неотрицательными координатами, последнее имеет место, если все элементы матрицы A положительные.
з10. УГибридФ методов ускорения сходимости монотонных приближений к решению x* уравнения вида x = Ax + f и однопараметрического итеративного агрегирования В данном параграфе предлагается один вариант метода, позволяющего строить приближения к решению системы линейных уравнений вида (8.2), обладающего достаточно высокой скоростью сходимости. Заметим, что предлагаемый вариант по существу представляет собой сочетание методов итеративного агрегирования и использует идею ускорения сходимости для известного варианта [36] ускорения сходимости метода последовательных приближений. Предлагаемый в данном параграфе метод по существу гарантирует достаточно высокую скорость сходимости к исходному решению и отличается простотой в его реализации. Немаловажной особенностью этого метода является то, что этот метод способен сходится к решению уравнения вида (8.2) и в случае, когда спектральный радиус матрицы A больше единицы r ( A) > 1. Сущность данного УгибридаФ методов для отыскания решения уравнения вида x = Ax + f, где A - матрица (10.1) порядка (n n ), f - свободный вектор, f R n, x - неизвестный вектор, x R n, заключается в следующем алгоритме. Сначала находим такие векторы u0,v0, для которых выполняются неравенства:
u0 u1 = Au0 + f, v1 = Av0 + f v0 r ( A) < 1 ). (10.2) (10.3) (существование таких векторов будет обеспечено при выполнении условия Алгоритм поиска векторов u0 и v0 был описан в з2. Затем из уравнения вида u = Au + f, по u0 строим u1 методом однопараметрического итеративного агрегирования и из уравнения вида 87 v = Av + f по v0 строим v1 методом однопараметрического итеративного p1 и q1 следующим агрегирования. Потом определяем поправочные коэффициенты образом. Пусть p1, q1 - такие два числа, для которых выполняются неравенства:
u1 u0 p1 (v0 v1 ), v0 v1 q1 (u1 u0 ).
Здесь p1 и q1 определяются из условия p1 ( u1 u0 )i ;
( v0 v1 )i q1 ( v0 v1 )i ( u1 u0 )i (i = 1,2,...).
В частности можно положить p1 = min i = 1, n ( u1 u0 )i (v v ) ;
q1 = min 0 1 i. i = 1, n ( u u ) ( v0 v1 )i 1 0i Тогда решение уравнения вида (10.1) между элементами u1*, v1*, где * u1 = на первой итерации заключено u1 + p1v1, 1 + p * v1 = v1 + q1u1. 1 + q Итак, выше был описан один шаг рекуррентного процесса предлагаемого метода. Аналогично, пусть определены un и vn, по индукции положим * un = un + pn vn, 1 + pn * vn = vn + qn un. 1 + qn Отметим тот факт, что при применении схемы ускорения сходимости поправочные коэффициенты p и q можно определять другим способом (отличным от описанного выше). Он заключается в следующем: а) возьмем отношения (u1 u0 ) i (v0 v1 ) i, (v0 v1 ) i (u1 u0 ) i (i = 1,2,...) б) в качестве p1 выбираем среднее арифметическое, составленное из соответствующих координат вектора (u1 u0 ) i, а в качестве (v0 v1 ) i q1 среднее арифметическое из соответствующих координат вектора, (v0 v1 ) i. (u1 u0 ) i Но как показывают примеры, если определены начальные приближения u0 и v0, удовлетворяющие условиям (10.2) и (10.3), то возможна такая ситуация, при которой УгибридФ методов ускорения сходимости ** u n, vn монотонных приближений и однопараметрического итеративного агрегирования не работает, т.к. на некотором шаге при определении недопустимая операция (деление на ноль).
* * Отметим, что последовательности un и vn обладает более высокой будет появляться скоростью сходимости к точному решению x*, чем метод ускорения сходимости. Пример 1. Рассмотрим уравнение вида (10.1), где 0.2 0.3 A= 0.4 0.2, 1 f =. 2 2.692307. Пусть 3. Спектральный радиус r ( A) = 0.546. Точное решение x* = 1 2.5 z0 =, тогда u0 = 1 2.5, 2.5 v0 =. 2. * * Соответствующие приближения un и vn, к координатам вектора решения представим в виде таблицы. Таблица 19 Приближения к 1-ой координате вектора решения n * У un Ф * У vn Ф 1 2.6667 Деление на ноль 2. Приближения к 2-ой координате вектора решения 1 2 4.000 Деление на ноль 4. В рассмотренном выше примере недопустимая операция возникла из-за действия параметра, при определении последовательностей un и vn методом последовательных приближений. Но как показывают практика в качестве начальных приближений можно выбрать такие неотрицательные векторы u0 и удовлетворять условиям (10.2) v0, которые не будут полученные и (10.3), но при этом * * последовательности un и vn будут сходится к точному решению x*, хотя это решение не всегда будет заключено между этими последовательностями. При этом скорость сходимости в некоторых случаях заметно увеличится. Здесь, * * по сути, мы имеем две независимые последовательности un и vn, сходящиеся к точному решению x* уравнения вида (10.1). Рассмотрим соответствующий пример. Пример 2. Рассмотрим уравнение вида (10.1), где 0.3 0.4 0.1 A = 0.1 0.5 0.2, 0.2 0.3 0.4 * 1 f = 2. 10.17391304 Точное решение x = 11.73913043, а спектральный радиус r ( A) = 0.828. 14.26086956 В качестве начальных приближений возьмем векторы:
1 u0 = 2, 3 5 v0 = 7. * * Используя вышеизложенный метод, получим приближения un и vn, между которыми заключено решение исходного уравнения.
* * Соответствующие приближения un и vn, к координатам вектора решения представим в виде таблицы.
Таблица 19 Приближения к 1-ой координате вектора решения n * У un Ф * У vn Ф 1 2 6 9 12 15 1 2 6 9 12 15 1 2 6 9 12 12.44537815 10.65854778 10.17369452 10.17391466 10.17391306 10.17391304 13.00840336 12.94980838 11.73867845 11.73913495 11.73913048 11.73913043 14.54621849 15.60339011 14.26039228 14.26087469 14.26086961 14. 12.466832216 10.43895004 10.17378128 10.17391530 10.17391305 10.17391304 13.00510274 12.16330283 11.73872240 11.73913590 11.73913048 11.73913043 14.52806509 14.67062656 14.26039700 14.26087558 14.26086962 14. Приближения к 2-ой координате вектора решения Приближения к 3-й координате вектора решения Как видно из таблицы точность вычислений на 15-м шаге составляет 10-8.
* * При реализации данного метода значения последовательностей un и vn можно находить для некоторых фиксированных значений последовательностей un и vn, т.е определять значения последовательностей * * un и vn в УузловыхФ точках последовательностей un и vn, при этом скорость схождения возрастает.
приближений к решению исходного уравнения заметно Применим данные рассуждения для вышеизложенного примера, причем значения u * и v* будут определяться для u4 n, v4 n. В качестве начальных приближений возьмем следующие векторы:
6 u0 = 5, 4 1 v0 = 2 * * Соответствующие приближения un и vn, к координатам вектора решения представим в виде таблицы. Таблица 20 Приближения к 1-ой координате вектора решения n * У un Ф * У vn Ф 1 2 3 4 1 2 3 4 1 2 3 11.05524862 10.16937891 10.17391086 10.17391304 8.64088398 11.73508279 11.73912821 11.73913042 9.47513812 14.25823541 14.26086792 14. 11.41860465 10.17410479 10.17391655 10.17391306 6.27906977 11.73888093 11.73913563 11.73913046 6.02325581 14.26040731 14.26087442 14. Приближения к 2-ой координате вектора решения Приближения к 3-й координате вектора решения Понятно, что если повысить порядок УузловыхФ точек, то скорость схождения к вектору решения исходного уравнения увеличится.
Можно при помощи следующего графика провести сравнительный анализ рассмотренных ранее численных методов.
120 Количество итераций 80 60 40 20 0 1 2 3 4 5 6 Порядок точности метод последовательных приближений метод ускорения сходимости гибрид ускорения сходимости гибрид ускорения сходимости (узл.) Рис. 1. Сравнение скорости сходимости гибрида методов ускорения сходимости и однопараметрического итеративного агрегирования известными ранее методами. В данном графике по оси абсцисс указаны количество верных знаков после запятой, а по оси ординат - количество итераций. В заключении отметим, что условие монотонной сходимости приближений к решению x* уравнения вида (10.1), при решении их гибридом методов ускорения сходимости и однопараметрического итеративного агрегирования в рассмотренных примерах не выполняется. с з11. Об одном варианте метода ускорения сходимости монотонных приближений к решению уравнения вида x = Ax + f В этом параграфе приближения УснизуФ и УсверхуФ к точному решению x* операторного уравнения вида x = Ax + f, (11.1) где A - матрица порядка (n n), f - свободный вектор, f R n, x неизвестный вектор, x R n, строятся по методу ускорения сходимости монотонных приближений (см.з2) к точному решению x* уравнения вида (11.1) по следующим формулам[36]:
* un = un + pn vn, 1 + pn * vn = vn + qn un. 1 + qn (11.2) При построении приближений (11.2) возникают проблемы с выбором начальных приближений u0, v0, для которых выполняются следующие неравенства:
u0 u1 = Au0 + f, v1 = Av0 + f v0 (11.3) (11.4) (существование таких векторов обеспечивает условие r ( A) < 1 ). И если в качестве вектора u0 всегда можно выбрать свободный вектор f, то с вектором v0 дела обстоят несколько сложнее (существует определенный алгоритм отыскания u0, v векторов предлагается u0, v0 ).
Здесь в качестве начальных по приближений выбрать векторы, полученные следующим формулам (см.з7):
xn + p + xn + p + 1 ( xn + p xn ), ( xn + p xn ), где xn p, xn, xn + p (n = 0,1,2,...) соответствующие приближения к решению x* метода последовательных приближений:
xn +1 = Axn + f, (n = 0,1,2,...) постоянная такова, что < [0,1) и при этом выполняется неравенство:
(xn xn p ) xn + p xn постоянная такова, что [0,1) и при этом выполнено неравенство:
xn + p xn (xn xn p ).
Заметим, что в данном случае векторы u0, v0 будут находиться в определенной близости от точного решения x* ( u0 x* v0 ) и при этом для них будут выполняться неравенства (11.3) и (11.4). Отметим, что данный выбор векторов u0, v0 увеличивает скорость сходимости двусторонних приближений к точному решению x* уравнения (11.1). Проиллюстрируем вышесказанное на соответствующем примере. Пример 1. Пусть дано уравнение вида (11.1), где.. 0.3 0.2 01 012 1... 0.26 015 017 01, f = 1. A= 013 0.28 019 0.21 1..... 011 01 0.2 018 Заметим, что в данном примере спектральный радиус r ( A) = 0.702, а 3.41546595 * 3.31263729. Здесь n=2, p=1 и для получения векторов точное решение x = 3.70159569 2.98449283 1 1 в качестве начального приближения выберем вектор x0 =. Тогда 1 u0, v получим следующие векторы u0, v0 :
3.40838 3.30559, u0 = 3.69403 2.97868 3.42103 3.31776. v0 = 3.70814 2. Теперь по формулам (11.2) получим соответствующие приближения УснизуФ и УсверхуФ к точному решению x* уравнения (11.1). Представим эти приближения в виде следующей таблицы. Таблица n * У un Ф * У vn Ф 3.414455 3.311699 3.700482 2.983718 3.414966 3.312155 3.701045 2.984086 3.415408 3.312582 3.701531 2.984445 3.415462 3.312634 3.701591 2.984490 3.415465 3.312637 3.701595 2. 3.416105 3.313286 3.702322 2.985073 3.415889 3.313043 3.702075 2.984844 3.415521 3.312690 3.701657 2.984538 3.415469 3.312640 3.701599 2.984495 3.415465 3.312637 3.701595 2. Итак, на 29-м шаге точность вычислений составляет 10-6, а на 40-м шаге точность вычислений составляет уже 10-8. Отметим тот факт, что при построении приближений, сходящихся к точному решению x* данного примера, методом последовательных приближений точность 10-6 достигается только на 45-м шаге.
Для сравнения построим в этом примере приближения методом ускорения сходимости монотонных приближений (см.з2).
1 1 Здесь для определения векторов u0, v0 выберем вектор z0 =. Тогда по 1 алгоритму описанному в з2, получим следующие векторы u0, v0 :
5.263 5.263, u0 = 5.263 5.263 5.263 5.263. v0 = 5.263 5. Тогда по формулам (11.2) получим соответствующие приближения УснизуФ и УсверхуФ к точному решению x* уравнения (11.1). Представим эти приближения в виде следующей таблицы. Таблица 22 Номер прибли жений n * У un Ф * У vn Ф 2.010526 1.954385 2.136842. 1828070 3.059012 2.971437 3.303166 2.694060 3.383679 3.282047 3.666129 2. 4.789473 4.578947 5.263157. 4105263 3.658175. 3549311 3.971307. 3188090 3.441629 3.337815 3.730788 3. 3.411640 3.308956 3.697327 2.981350 3.415005 3.312194 3.701082 2.984114 3.415461 3.312632 3.701590 2.984488 3.415465 3.312636 3.701595 2. 3.418614 3.315667 3.705108 2.987079 3.415844 3.313001 3.702018 2.984804 3.415469 3.312641 3.701599 2.984496 3.415466 3.312637 3.701596 2. Итак, на 40-м шаге точность вычислений составляет 10-6. А теперь рассмотрим предложенный метод в случае УгибридаФ методов итеративного агрегирования и метода ускорения монотонных приближений [73]. Следует отметить, что в этом случае, при помощи векторов u*, v*, мы можем получить лишь оценку точного решения x*. Реализуем это на уже рассматриваемом здесь примере 1. Тогда здесь векторы u0, v0 :
3.40838 3.30559, u0 = 3.69403 2.97868 3.42103 3.31776. v0 = 3.70814 2. Приближения, полученные по формулам (11.2) представим в виде следующей таблицы.
Таблица 23 Номер прибли жений n * У un Ф * У vn Ф 3.415420 3.312682 3.701559 2.984511 3.415452 3.312628 3.701587 2.984494 3.415463 3.312635 3.701595 2.984492 3.415465 3.312637 3.701595 2. 3.415420 3.312628 3.701559 2.984511 3.415451 3.312628 3.701586 2.984495 3.415463 3.312635 3.701595 2.984492 3.415465 3.312637 3.701595 2. Итак, здесь уже на 4-м шаге точность вычислений составляет 10-6, а на 8м шаге точность вычислений составляет уже 10-8. По сравнению с предыдущими случаями, здесь заметно возросла скорость сходимости приближений. Проведем сравнительный анализ используемых в этом параграфе численных методов при помощи следующего графика.
60 Количество итераций 40 30 20 10 0 1 2 3 4 5 6 Порядок точности вариант метода ускорения сходимости метод ускорения сходимости "гибрид" методов ОИА и метода ускорения Рис. 2. Сравнение варианта метода ускорения сходимости с другими численными методами. По предложенному методу автором разработана программа на языке программирования TURBO PASCAL.
з12. Об одном варианте метода Зейделя Балансовая модель производства является одной из наиболее простых математических моделей. Она записывается в виде системы уравнений, каждое из которых выражает требование равенства (баланса) между количеством продукции, производимой отдельным экономическим объектом, и совокупной потребностью в этом продукте. Балансовые модели основываются на понятии межотраслевого баланса, который представляет собой таблицу, характеризующую связи между отраслями (экономическими объектами) экономической системы. В настоящее время большое число работ посвящается этой модели и ее применению для решения различных задач. Такой интерес к балансовой модели определяется тем, что, оказалось, эта модель хорошо отражает многие существенные особенности современного производства и в то же время легко поддается расчету. Во многих странах мира балансовый метод используется для экономического анализа, планирования и прогнозирования. Система балансовых уравнений может быть записана в матричной форме в виде следующего уравнения x=Ax+f. Здесь используется терминология теории положительных операторов [36]. Для того чтобы изложить суть предлагаемого варианта численного метода предварительно опишем метод Зейделя и метод ускорения сходимости приближений. Одна из возможных интерпретаций метода Зейделя, изложенная в [16], решения линейных алгебраических систем и более общих операторных уравнений вида x = Ax + f, (12.1) заключается в следующем. Если требуется решить уравнение где x - неизвестный элемент некоторого банахова пространства Е, f - заданный элемент из Е, А- линейный оператор, действующий в Е, то при условии, что А=А1+А2 и в предположении, что существует оператор обратный к оператору (I-A1), уравнение (12.1), можно переписать в эквивалентном виде x = ( I A1 ) 1 A2 x + ( I A1 ) 1 f, (12.2) после чего к полученному уравнению применить метод последовательных приближений xm+1 = (I A1 ) A2 xm + (I A1 ) f, 1 (m = 1,2,...), который можно также записать в виде y m +1 = A1 y m +1 + A2 y m + f (m = 1,2,...).
(12.3) Т.е. по сути, применять метод последовательных приближений для решения операторного уравнения вида x = Dx + h, (12.4) где D = (I A1 )1 A2, h = (I A1 )1 f. Именно такую интерпретацию допускает классический метод Зейделя решения линейных систем алгебраических уравнений. Для того, чтобы этот метод был реализуем, достаточно, чтобы число = 1 не являлось точкой спектра оператора А1, а для этого, в частности, достаточно, чтобы спектральный радиус r(A1) оператора А1 удовлетворял неравенству r(A1)<1.
(12.5) При этом для определенных классов операторов А такое преобразование уравнения (12.1) (а именно, переход от уравнения (12.1) к вспомогательному и эквивалентному уравнению (12.2) ) обладает следующей ( I A1 ) 1 A2, полезной как было особенностью: спектральный радиус оператора установлено в [41], не больше, и, как правило, меньше спектрального радиуса r(A) оператора А в исходном уравнении (12.1). А это, в частности, обеспечивает, вообще говоря, более быструю сходимость последовательности {ym} к единственному решению x * уравнения (12.1) метода Зейделя (12.3) по сравнению с обычным методом последовательных приближений x m +1 = ( A1 + A2 ) x m + f (m = 0,1,...).
Более того, в этом случае удается получить явные оценки для эффекта ускорения сходимости метода Зейделя по сравнению с обычным методом последовательных приближений и указать другие алгоритмы построения еще более быстро сходящихся приближений к неизвестному решению x *. Рассмотрим уравнение (12.1) с матричным оператором А. В [41] было установлено, что для уравнения (12.1) при условии (12.5), метод Зейделя монотонно зависит от выбора матрицы А1, а именно, с возрастанием количества ненулевых элементов матрицы А1 скорость сходимости метода (12.3) возрастает, точнее говоря не уменьшается.
Это можно интерпретировать следующим образом: чем большую часть А1 матрицы А мы оставляем в обращаемой части ( I A1 ) уравнения, тем быстрее приближения, полученные по методу Зейделя (12.3), сходятся к решению x *. Уместно, однако, сразу заметить при этом, что с возрастанием доли А1, вообще говоря, усложняется процедура определения приближений по методу Зейделя, эта процедура будет самой простой, если в качестве А1 брать нижнюю треугольную часть матрицы А, т.е. полагать y i( m +1) = a ij y (jm +1) + a ij y (jm ) + f i, j =1 j =i i 1 n (i = 1, n ) (12.6) что как раз соответствует классической схеме метода Зейделя. Если же присоединить к матрице А1 еще и главную диагональ, то в этом случае метод Зейделя примет несколько нетрадиционный вид:
y i( m +1) = a ij y (jm +1) + a ij y (jm ) + f i, j =1 j =i +1 i n (i = 1, n ), (12.7) т.е. примет вид неявной схемы, при которой для определения (m+1) - го приближения по компоненте с номером i, т.е. при определении y i( m +1) нам придется решать для каждого i одно скалярное уравнение с неизвестным y i( m +1). Этот метод назовем методом Зейделя первого порядка.
Аналогичным образом определяются методы Зейделя второго и более высоких порядков. Тем самым, чем большая часть матрицы А будет включаться в А1, тем сложнее будет фактически реализация метода Зейделя, т.к. с ростом матрицы А1 возрастает порядок системы уравнений, которую приходится решать для определения каждого следующего приближения, и соответственно, усложняется схема реализации метода Зейделя. В классической схеме метода Зейделя порядок соответствующей системы фактически равен нулю. Понятно, что применение неявных схем требует решения вспомогательных систем линейных уравнений. Количество неизвестных в этих системах прямо зависит от порядка метода Зейделя. Оно тем больше, чем выше порядок. В любом случае при применении метода Зейделя невысокого порядка, порядок соответствующей системы, вообще говоря, меньше числа k - порядка исходной системы линейных алгебраических уравнений, и потому применение соответствующей схемы является более простым, нежели решение исходной системы n - уравнений с n - неизвестными. Итак, метод Зейделя осложняется в реализации с ростом матрицы А1, и потому, естественно, на эту более сложную схему метода Зейделя имеет смысл идти лишь в том случае, если при этом улучшается скорость сходимости. Оказывается, что именно так и обстоит дело, что следует из теоремы, доказанной в [41] и приведенной в монографии [36]. Теорема 12.1. Пусть А, r(A)<1, и оператор А1 переводит каждый внутренний элемент конуса n R+ неотрицательных векторов пространства R n во внутренний элемент. Тогда имеет место неравенство r[ (I A1 )1 A2] поэтому уравнение (12.4) имеет единственное решение x *, которое является пределом последовательных приближений x n +1 = Dx n + h, (n = 0,1,2,...) при любом начальном приближении x 0 E. Допустим, что начальное приближение x 0 = u 0 выбрано так, что u 0 Du 0 + h. (12.8) Тогда последовательные приближения u n +1 = Du n + h (12.9) будут удовлетворять соотношениям u 0 u1... u n u n +1... x *. (12.10) x0 = v Аналогично, соотношению если начальное приближение удовлетворяет v 0 Dv 0 + h, (12.11) то последовательные приближения v n +1 = Dv n + h (12.12) удовлетворяют соотношениям x *... v n +1 v n... v1 v 0. (12.13) Таким образом, если удается найти элементы u 0 и v 0, удовлетворяющие соответственно соотношениям (12.8) и (12.11), то мы получаем монотонные приближения к точному решению x * операторного уравнения (12.4). Наличие двусторонних монотонных приближений дает одновременно оценку погрешности: если приближенным значениям решения x * считать элемент 1 (u n + v n ), то из (12.10) и (12.13) вытекает оценка 2 1 (v n u n ) 1 (u n + v n ) x * 1 (v n u n ). 2 2 Основную трудность составляет отыскание начальных приближений u 0 и v 0. В [36] указан алгоритм отыскания таких начальных приближений. Изложим его суть. Пусть z 0 - внутренняя точка конуса K. Если r ( D) < 1, то обязательно найдется номер r, такой, что для данного вектора z 0 выполнено неравенство: D r z 0 z 0, обязательно будет где < 1. Тогда элемент z1 = 1 1 r z0 + 2 r Dz 0 +... + D r 1 z удовлетворяет неравенству Dz1 z1. 1 r (12.14) Не ограничивая общности можно считать, что z1 является внутренним элементом конуса K. Поэтому для некоторого вещественного b > 0 будет выполнено следующее неравенство: b(1 r ) z1 h b(1 r ) z1. 1 (12.15) Положим тогда u 0 = bz1, v 0 = bz1. (12.8) Эти элементы удовлетворяют соотношениям и (12.11). Действительно, в силу (12.14) Du 0 + h = b Dz1 + h b 1 / r z1 + h, и (12.8) вытекает из левой части неравенств (12.15). Аналогично Dv 0 + h = b Dz1 + h b r z1 + h b r z1 + b(1 r ) z1 = v 0. 1 1 Конечно, в различных частных случаях элементы u 0 и v 0 можно выбирать более простым способом. Например, если h K, то в качестве u 0, конечно, можно выбирать элемент h. Пусть u 0 и v 0 удовлетворяют соответственно соотношениям (12.8) и (12.11). Будем считать дополнительно, что выполнены неравенства u1 u 0 p1 (v 0 v1 ), v 0 v1 q1 (u1 u 0 ), (12.16) где одно из чисел p1 и q1 положительно (при p1 = q1 = 0 совпадают с (12.8) и (12.11) ). Определим тогда элементы * u1 = эти неравенства u1 + p1 v1, 1 + p1 v1 + q1u1. 1 + q (12.17) (12.18) * v1 = Теорема 12.2. Справедливы соотношения * * u1 u1 x * v1 v1. (12.19) Доказательство. Крайние неравенства в (12.19) вытекают непосредственно из (12.17), Очевидно, (12.18) и из неравенства Du 0 + h Dv 0 + h. * * Du1 + h u1 = 1 [D(Du 0 + h u 0 ) + p1 D(Dv 0 + h v 0 )] 1 + p и в силу (12.16) * * Du1 + h u1. Это значит, что элемент u1* удовлетворяет условию (12.8). Как нам уже известно, из этого условия вытекает, что u1* x *. Аналогично * * v1 Dv1 + h = ( ) 1 [D(v 0 Dv0 h ) + q1 D(u 0 Du 0 h )]. 1 + q Значит, v1* удовлетворяет (12.11), и поэтому v1* x *. Теорема доказана. Формулы (12.17) и (12.18) можно рассматривать как рекуррентный * * процесс построения последовательностей u n, v n. Теорема 12.2 означает, что этот рекуррентный процесс сходится не медленнее последовательностей (12.9) и (12.12), и сохраняет монотонность последовательных приближений. Многочисленные примеры показывают, что в достаточно общих условиях процесс (12.17) и (12.18) сходится существенно быстрее обычного метода последовательных приближений. Рассмотрим реализацию предложенного варианта метода Зейделя на конкретных примерах. Пример 1. Пусть дано уравнение вида (12.1), где 0.15 0.18 A = 0.19 0.27 0.33 0.31 0.36 0.16 0.14 0.22 0.14 0.17 0.21 0.12 0.21 0.21 0.15 0.25 0.13 0.2 0.15 0.14 0.18, 0.24 0.19 1 1 f = 1. 1 454.9612529 474.9256427 Точное решение уравнения x * = 468.4250761, а спектральный радиус 433.8284457 545.3775432 r ( A) = 0.9975. При решении примера в данном случае метод Зейделя имеет порядок ноль. Используя вышеизложенный метод ускорения сходимости, получим * * приближения un и vn. * * Соответствующие приближения un и vn, к координатам вектора решения представим в виде таблицы. Таблица n * У un Ф * У vn Ф Приближения к 1-ой координате вектора решения 1 541 1434 2009 2957 4196 5000 1 541 1434 2009 2957 4196 5000 1 541 1434 2009 2957 4196 5000 1 541 -31581.165783 2.457779 440.958437 453.467382 454.923932 454.960952 454.961239 -32943.148882 2.744047 460.313883 473.366807 474.886699 474.925329 474.925629 -32450.640618 3.251564 454.030183 466.889377 468.386711 468.424767 468.425062 -29994.511930 3.465972 33302.009434 906.048065 468.920229 456.450447 454.998456 454.961552 454.961266 34738.487582 945.628970 489.491656 476.479597 474.964463 474.925955 474.925656 34219.583220 932.142260 482.774902 469.955967 468.463321 468.425384 468.425089 31630.236737 862. Приближения к 2-й координате вектора решения Приближения к 3-й координате вектора решения Приближения к 4-й координате вектора решения 1434 2009 2957 4196 5000 1 541 1434 2009 2957 4196 5000 графика. 7000 Количество итераций 420.510788 432.407670 433.792951 433.828160 433.828433 -37631.653423 5.420638 528.668463 543.594958 545.333010 545.377184 545. 447.104409 435.244773 433.863828 433.828730 433.828458 39686.310105 1083.643995 562.034312 547.154547 545.421936 545.377900 545. Приближения к 5-й координате вектора решения Проиллюстрируем данные вычисления при помощи следующего 5000 4000 3000 2000 1000 0 1 2 3 Порядок точности Рис.3. Вариант метода Зейделя (порядок л0). Книги, научные публикации