Об итерационных методах решения операторных уравнений второго рода
Диссертация
Математика и математический анализ
Метод ускорения сходимости монотонных приближений к решению уравнения. Построение приближений, сходящихся к спектральному радиусу и собственному вектору линейного оператора. Построение приближений, сходящихся к собственному вектору линейного оператора. Об одном варианте метода Зейделя.
Русский
2013-01-06
1.44 MB
56 чел.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РФ
СТАВРОПОЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
______________________________________________________
На правах рукописи
Плюта Алексей Иванович Об итерационных методах решения операторных уравнений второго рода
Специальность 05.13.18. – «математическое моделирование, численные методы и
комплексы программ»
Диссертация
на соискание ученой степени
кандидата физико-математических наук
Научный руководитель –
доктор физико-математических наук,
профессор, член-корреспондент
АН Таджикистана,
академик МАИ В.Я. Стеценко
Ставрополь – 2004
2 ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ…………………………………………………………………….
4
ГЛАВА 1. Обзор литературы…………………………………………………
8
§1.Метод последовательных приближений................................................... 8 §2. Метод ускорения сходимости монотонных приближений к решению
уравнения вида x = Ax + f ……………………………………………………..
15
§3. Метод однопараметрического итеративного агрегирования решения
линейных операторных уравнений вида x = Ax + f , где оператор A - мат-
рица n - го порядка……………………………………………………………. 21 §4. Метод однопараметрического итеративного агрегирования решения
нелинейных операторных уравнений вида x = F(x) + f , где F(x) - нели-
нейный оператор……………………………………………………………… 27 ГЛАВА 2. Построение приближений, сходящихся к спектральному ра-
диусу и собственному вектору линейного оператора……………………… 32 §5. Построение приближений, сходящихся к спектральному радиусу ли-
нейного оператора…………………………………………………………….. 41 ГЛАВА 3.Развитие методов построения приближений, сходящихся к
точному решению операторного уравнения видаx = Ax + f ………………. 56
§7. Об одном итерационном методе решения системы линейных алгеб-
раических уравнений вида x = Ax + f с квадратной матрицей A , в случае,
когда спектральный радиус матрицы A , больше чем единица…………….
56
§8. Получение двусторонних оценок точного решения * x операторного
уравнения вида x = Ax + f , в случае, когда спектральный радиус опера-
тора A не обязательно меньше единицы…………………………………….
65
§9. О некоторых подходах к уточнению границ решения операторных
уравнений вида x = Ax + f в случае, когда спектральный радиус операто- 73
ра A не обязательно меньше единицы. §10.“Гибрид” методов ускорения сходимости монотонных приближений
к решению * x уравнения вида x = Ax + f и однопараметрического итера-
3
тивного агрегирования……………………………………………………….. 86 §11. Об одном варианте метода ускорения сходимости монотонных при-
ближений к решению уравнения вида x = Ax + f …………………………....
93
§12. Об одном варианте метода Зейделя……………………………………. 100 ЗАКЛЮЧЕНИЕ……………………………………………………………….. 112 ЛИТЕРАТУРА………………………………………………………………… 114 ПРИЛОЖЕНИЕ……………………………………………………………….. 121
4 Введение
При решении широкого класса задач математического анализа, алгебры,
экономики требуется находить решение операторных уравнений. В тех слу-
чаях, когда процесс отыскания точного решения является затруднительным,
на помощь приходят итерационные методы, позволяющие найти прибли-
женное решение с определенной степенью точности. Соответствующий
класс задач можно представить с помощью операторного уравнения вида x = Ax + f (1)
с линейным или нелинейным оператором А, действующим в банаховом простран-
стве Е, и свободным членом f из этого пространства.
Большое практическое значение приобретает возможность строить приближения u и, соответственно, v к решению * x операторного уравнения вида (1), та- n n
кие что u ≤ x* ≤ v
n n
При этом, оказывается, параллельно решаются две важные задачи теории
приближенных методов решения операторных уравнений – задача об оценке
погрешности приближенного решения, а также задача об априорной оценке
относительной погрешности приближенного решения.
Использование современных ЭВМ открывает широкие возможности для
решения таких задач. Математическое моделирование стало активно вне-
дряться в практику научных и прикладных разработок при исследовании
сложных явлений и процессов, происходящих в экономике. Лишь с помощью
современных ЭВМ удается проводить численное моделирование достаточно
сложных экономических процессов.
Существенные прикладные преимущества, проведенные исследования прак-
тической скорости сходимости итерационных процессов к точному решению * x
операторного уравнения вида (1), возможность контроля результатов в процессе
решения и наличие математических обоснований, дают повод обратить серьез-
ное внимание на итерационные методы не только как на объект интересных тео-
5
ретических исследований, но и как на новые подходы к организации и проведе-
нию реальных расчетов плановых задач большой размерности и сложной струк-
туры. Актуальность проблемы. Балансовая модель производства является одной
из наиболее простых математических моделей. Она записывается в виде системы
уравнений, каждое из которых выражает требование равенства (баланса) между
количеством продукции, производимой отдельным экономическим объектом, и
совокупной потребности в этом продукте. Отсюда происходит название модели.
Впервые балансовые модели начали использоваться в СССР в 20-х годах. В
более или менее законченном виде теория балансовых моделей была разработана
американским ученым В.В. Леонтьевым в середине 30-х годов. Однако в те годы
ни уровень развития математической науки, ни качество вычислительной техники
не позволили широко распространить балансовый метод.
За разработку и внедрение в практику метода межотраслевого баланса группа
советских экономистов под руководством академика А.Н. Ефимова в 1968 году
была удостоена Государственной премии СССР. В настоящее время большое ко-
личество работ посвящается этой модели и ее применению для решения различ-
ных задач. Такой интерес к балансовой модели определяется тем, что, как оказа-
лось, эта модель хорошо отображает многие существенные особенности совре-
менного производства и в то же время легко поддается расчету. Во многих стра-
нах мира балансовый метод используется для экономического анализа, планиро-
вания и прогнозирования.
В связи с внедрением ЭВМ в научные разработки, значительно повысился
интерес к различным численным методам и алгоритмам, реализация которых гра-
ничит с проведением вычислительного эксперимента. Потребность в таком под-
ходе к решению задач математической экономики диктуется все усложняющими-
ся запросами практики, а также связана с попыткой создания более рациональных
и более общих теоретических моделей для изучения сложных экономических яв-
лений.
6
Активное использование методов численного моделирования позволяет рез-
ко сократить сроки научных и конструкторских разработок. Цели работы - приближенное решение операторных уравнений вида (1)
в случаях, когда спектральный радиус ρ(A) оператора A не обязательно
меньше единицы; построение итерационных последовательностей сходя-
щихся к решению уравнения (1), к собственным значениям и собственным
векторам оператора A ; разработка новых методов, повышающих скорость
сходимости итераций к решению уравнения (1); разработка соответствующе-
го программного обеспечения, позволяющего реализовать предложенные ме-
тоды. Научная новизна результатов работы. Развитие теории линейных и
нелинейных операторов, действующих в полуупорядоченных банаховых
пространствах. Так, например, предложены развития методов решения опе-
раторных уравнений вида (1) в случаях, когда у оператора A спектральный
радиус r(A) не обязательно меньше единицы. Предложен метод построения
двусторонних оценок точного решения * x операторного уравнения вида (1) в
случае, когда спектральный радиус оператора A не обязательно меньше
единицы. Предложены варианты методов, позволяющие строить приближе-
ния к решению уравнений вида (1), обладающие высокой скоростью сходи-
мости. Разработано программное обеспечение на языке программирования
TURBO PASCAL, реализующее предложенные итерационные методы. Достоверность результатов работы вытекает из математической строго-
сти постановки и решения исследуемых задач, а также из совпадения ряда
полученных результатов в частных случаях с известными в литературе. Практическая значимость работы заключается в возможности приме-
нения полученных методов решения уравнения (1) при решении конкретных
задач математики и экономики. Отдельные результаты могут быть использо-
ваны при чтении специальных курсов и подготовке учебных пособий.
На защиту выносятся следующие положения:
7
- итерационный метод решения системы линейных алгебраических уравне-
ний вида (1) с квадратной матрицей A , в случае, когда наибольшее по мо-
дулю собственное значение матрицы A , больше чем единица;
- методы получения двусторонних оценок точного решения * x операторного
уравнения вида (1), в случае, когда спектральный радиус оператора A не
обязательно меньше единицы, а также подходы к уточнению полученных
оценок;
- синтез методов ускорения сходимости монотонных приближений к реше-
нию * x уравнения вида (1) и однопараметрического итеративного агреги-
рования;
- метод ускорения сходимости монотонных приближений к решению урав-
нения вида (1), в случае выбора в качестве начальных приближений векто-
ров, которые ограничивают точное решение * x уравнения вида (1) «сверху«
и «снизу»;
- вариант метода Зейделя, позволяющий строить приближения, сходящиеся к
точному решению * x уравнения (1) с помощью метода ускорения сходимо-
сти.
Структура и объем диссертации. Диссертация состоит из введения и
трех глав, заключения, списка литературы и приложения. В ней принята
сквозная нумерация параграфов, для утверждений и формул введена
двойная нумерация, включающая номер параграфа и порядковый номер
утверждения или формулы в нем. Диссертация изложена на 167 страни-
цах, список использованной литературы содержит 82 наименования.
8 ГЛАВА 1. ОБЗОР ЛИТЕРАТУРЫ §1.Метод последовательных приближений
Одним из наиболее известных итерационных методов решения систем ли-
нейных уравнений является метод последовательных приближений [4] (ме-
тод простой итерации). Система уравнений Ax = b
тем или иным методом преобразуется к виду уравнения “второго рода”: x = Bx + f
)
1
.
1
(
после чего его решение находится как предел последовательности x : m+1 x
= Bx + f , (m =
,
1
,
0
,...)
2
)
2
.
1
(
m+1 m
где B - матрица порядка (n × n) , f - свободный вектор, n f ∈ R , x - неизвест-
ный вектор, n x ∈ R , x0 - начальное приближение. Метод
)
2
.
1
(
называется ме-
тодом простой итерации. Теорема 1.1. (о достаточном условии сходимости метода простой ите- рации) Если норма матрицы B меньше единицы: B < 1, то система уравне- ний
)
1
.
1
( , при любом свободном члене n f ∈ R , имеет единственное решение и итерационный процесс
)
2
.
1
( сходится к решению *
* x = x ( f ) со скоростью геометрической прогрессии:
* m x − x
≤ c ⋅ x − x ⋅ B , m =
,
1
,
0
,...
2
, c − const. m+1
1
0
Качество итерационного процесса удобно характеризовать скоростью
убывания отношения погрешности после m итераций к начальной погрешно-
сти:
|| x ||
|| m B x || S = sup m
= sup
0
|| m
= B || . m x ≠0 x
≠ x
0
||
|| x
0
||
||
0
0
0
Можно гарантировать, что величина S ≤ ε , если m B ≤ ε , т.е. при m
ln( 1
−
ε )
m ≥ m =
.
ε
ln(|| B || 1
− )
Если существуют постоянные γαβ, γβα такие, что при x ≠ 0
9
||x||β ≤γ x α
αβ, || || ≤ γ
,
||x||
βα
α
||x||β
то нормы x и x
α
β в n R называются эквивалентными.
Имеем
||rm|| ≤ γ ||rm|| ≤ γ ||B||m ||r0|| ≤ γ γ || || B m ||r0|| .
β
αβ
α
αβ
α
α
αβ βα
α
β
Таким образом, если условие изложенной выше теоремы выполнено для
нормы . , то утверждение справедливо относительно любой эквивалентной
α
ей норме.
Любые две нормы в конечномерном пространстве являются эквивалент-
ными. В частности, нормы x , x , x , вычисляемые соответственно по фор-
1
2
∞
мулам, m m
||x|| = ∑|x |, ||x|| = ∑|x |2 , || x || = max | x |
1 j
2 j
∞ j
1≤ j ≤ m j=1 j=1
эквивалентны между собой вследствие справедливости цепочки неравенств x ≤ x ≤ x ≤ m x .
∞
2
1
∞ Определение 1.1.Норма A называется согласованной с нормой x в про- странстве, если для каждого x из пространства векторов выполняется Ax ≤ c x , где с-const.
Согласованные с вышеперечисленными нормами в пространстве матриц
являются соответственно нормы m m A = max(
|
|) , i A = max λ
, A = max( | a |) ,
∞
∑
1
∑ a
*
≤ ij
1 j ≤ ij m
2
( A A
1≤i≤m
)
≤
1 i≤m i =1 j =1
где λi - собственные значения матрицы D = A* ⋅ A, а * A - матрица, сопряжен- D
ная к матрице A (т.е. это результат комплексного сопряжения к матрице
транспонированной по отношению к матрице A ).
При решении уравнения вида
)
1
.
1
(
методом последовательных приближе-
ний
)
2
.
1
(
по заданной точности ε > 0 вычислений бывает важно определить
число итераций " " m . Поясним как найти m - количество итераций, обеспечи-
10
вающих, для получения искомого решения системы
)
1
.
1
(
, приближение к
решению с точностью до ε .
При известных условиях к решению уравнения
)
1
.
1
(
сходится итераци-
онный процесс
)
2
.
1
(
, при любом начальном приближении x , при этом тако-
0
выми известными условиями является одно из следующих условий: n
a) max∑ a ≤ q ij
1 <1; i =1,n j=1 n
б) max∑ a ≤ q ji
2 <1; i=1,n j=1 n n
в) ∑ ∑ a2 ≤ q ij
3 <1. i=1 j=1
Пусть ε > 0 заданное число, тогда для того чтобы гарантировать неравен-
ство:
* qm x − x i
≤
⋅ x − x
< ε m+1
, (i = ,1 3
,
2 )
(i )
1 − q
1
0 (i) i
где x соответственно одна из следующих норм:
(i) n n
x
= max x
= ∑
2
= ∑ i , x x , x x ,
(1) i
2 i i=1,n
3 i=1 i=1
положив
ε 1
( − q )
ln i x − x
1
0 (i) z =
,
ln(q ) i
достаточно определить m по формуле: m = [z]+ ,
1
где [z] обозначает целую часть числа z (наибольшее целое число, не
превосходящее z ).
Отметим явные преимущества метода последовательных приближений:
- относительная простота построения последовательности x , сходящейся m
к решению уравнения
)
2
.
1
(
;
11
- легкость реализации метода на ЭВМ.
Недостатками метода последовательных приближений является, вообще
говоря, недостаточно высокая скорость последовательных приближений
)
2
.
1
(
, к решению уравнения
)
1
.
1
(
, особенно в тех случаях, когда наибольшее
по модулю собственное значение матрицы B , близко к единице.
Рассмотрим соответствующие примеры, когда по заданной точности ε
определяется количество приближений к вектору являющимся решением
данной системы уравнений.
В примере 1 выполняются все три условия (а,б,в). Пример 1. Рассмотрим систему уравнений вида
)
1
.
1
(
, где
0 4
.
0 4
.
0.
1
1
B = 0 3. 0 2
.
0.
4 , f = 1 .
01. 01.2 0. 3
1
5.337423
Заметим, что значение точного решения * x = 4.754601 а спектральный
3.006134
радиус оператора B : r(B) = 7707
.
0
. Используем метод
)
2
.
1
(
. В качестве на-
1
чального приближения выберем вектор x =
. Пусть ε = 0.0001. Получен-
0
1
1
ные значения последовательных приближений представим в виде таблицы. Таблица 1
№ п/п, m
Значения приближений x m
1 1.900000
1.900000
1.520000
2 2.672000
2.558000
1.874000
4 3.750516
3.450924
2.336384
10 5.004784 4.481399 2.865818
17 5.283694 4.710473 2.983470
28 5.334361 4.752086 3.004843
42 5.337343 4.754535 3.006101
12
52 5.337417 4.754596 3.006132
53 5.337418 4.754597 3.006133
На основании сказанного выше, имеют место оценки близости * x − x
< ε m
2
В данном примере m = 53.
Рассмотрим пример в котором не выполняется условие а). Пример 2. Рассмотрим систему уравнений вида
)
1
.
1
(
, где
0.4 0.6 0.1
1
B = 0.3 0.2 0.4 , f = 1 .
0.1 0.12 0.3
1
8.681318
Заметим, что значение точного решения * x = 6.387362 а спектральный
3.763736
радиус оператора B : r(B) = 8404
.
0
.
Используем метод
)
2
.
1
(
. В качестве начального приближения выберем
1
вектор x =
. Определим ε = 0.0001. Полученные значения последователь-
0
1
1
ных приближений представим в виде таблицы. Таблица 2
№ п/п, m
Значения приближений x m
1 2.100000
1.900000
1.520000
2 3.132000
2.618000
1.894000
8 6.723696
5.059942
3.106727
10 7.298678 5.449825 3.299700
20 8.438316 6.222588 3.682180
42 8.676017 6.383767 3.761957
62 8.681154 6.387251 3.763681
130 8.681318 6.387362 3.763736
152 8.681318 6.387362 3.763736
13
В данном примере m = 152. На основании сказанного выше, имеют место
оценки близости * x − x
< ε . m 2
Рассмотрим пример, в котором выполняется лишь условие в). Пример 3. Рассмотрим систему уравнений вида
)
1
.
1
(
, где
0.4 0.6 0.1
1
B = 0.3 0.2 0.4, f = 1 .
0.1 0.2 0.3
1
10
Заметим, что значение точного решения * x = .
7 5 , а спектральный радиус
5
оператора B : r(B) = 8662
.
0
.
Используем метод
)
2
.
1
(
. В качестве начального приближения выберем
1
вектор x =
. Определим ε = 0.00001. Полученные значения последователь-
0
1
1
ных приближений представим в виде таблицы. Таблица 3
№ п/п, m
Значения приближений x m
1 2.100000
1.900000
1.600000
2 3.140000
2.650000
2.070000
8 7.098880
5.451648
3.764142
25 9.747447
7.321683
4.892414
60 9.998342
7.498829
4.999293
100 9.999994 7.499996 4.999997
491 10.00000 7.500000 5.000000
777 10.00000 7.500000 5.000000
В данном примере m = 777 . На основании сказанного выше имеют место
оценки близости x − x
< ε . m 3
Проиллюстрируем пример у которого не выполняется ни одно из данных
условий (а,б,в).
14 Пример 4. Рассмотрим систему уравнений вида
)
1
.
1
(
, где
0.4 0.6 0.1
1
B = 0.3 0.2 0.4 , f = 1 .
0.1 0.3 0.3
1
12.474226
Заметим, что значение точного решения * x = 9.587628 , а спектральный
7.319587
радиус оператора B : r(B) = 8973
.
0
.
Используем здесь метод
)
2
.
1
(
. В качестве начального приближения выбе-
1
рем вектор x =
. После выполнения соответствующих действий замечаем,
0
1
1
что ни одно из данных условий не выполняется. При решении данного при-
мера методом последовательных приближений получим итерационный про-
цесс, сходящийся к точному решению * x , но, используя, изложенный выше
метод мы не можем определить количество итераций по заданной наперед
точности ε .
Отметим, что проиллюстрированные выше примеры были реализованы
при помощи разработанной автором программы на языке программирования
TURBO PASCAL.
Из приведенных примеров видно, что для одного и того же ε , номер при-
ближений, начиная с которого выполняется неравенство, бывает различным,
а это говорит о том, что для достижения одной и той же точности ε для при-
ближения к искомому вектору решения заданной системы уравнений прихо-
дится совершать различное количество приближений. В этой связи уместно
ввести характеристику, которую можно назвать скоростью сходимости мето-
да последовательных приближений. Эта скорость определяется числом тех
итераций, которые необходимо совершить для того, чтобы соответствующие
приближения x отличались от точного решения * x меньше чем на ε . Ока- m+1
зывается [10], что эта скорость определяется величиной спектрального ра-
диуса r(B) матрицы B .
15 §2. Метод ускорения сходимости монотонных приближений к решению уравнения вида x = Ax + f
Рассмотрим операторное уравнение вида x = Ax + f ,
(
)
1
.
2
где A - линейный положительный оператор относительно телесного нор-
мального конуса K в банаховом пространстве E , f некоторый вектор из E .
Предположим, что спектральный радиус r( ) A < 1; в этом случае уравнение
(
)
1
.
2
имеет единственное решение
* x , которое является пределом
последовательных приближений x
= Ax + f , (n =
,
1
,
0
,...)
2
n+1 n
при любом начальном приближении x ∈ E . Допустим, что начальное при-
0
ближение x = u выбрано так, что
0
0 u ≤ Au + f .
(
)
2
.
2
0
0
Тогда последовательные приближения u
= Au + f
n+1 n
будут удовлетворять соотношениям
* u ≤ u ≤ ... ≤ u ≤ u
≤ ... ≤ x .
(
)
3
.
2
0
1 n n 1
+
Аналогично, если начальное приближение x = v удовлетворяет соотно-
0
0
шению v ≥ Av + f ,
(
)
4
.
2
0
0
то последовательные приближения v
= Av + f
n+1 n
удовлетворяют соотношениям
* x ≤ ... ≤ v
≤ v ≤ ... ≤ v ≤ v .
(
)
5
.
2
n 1
+ n
1
0
Таким образом, если удается найти элементы u и v , удовлетворяющие
0
0
соответственно соотношениям ( )
2
.
2
и ( )
4
.
2
, то мы получаем монотонные
приближения по избытку и по недостатку к точному решению * x оператор-
ного уравнения ( )
1
.
2
. Наличие двусторонних монотонных приближений дает
16
одновременно оценку погрешности: если приближенным значениям решения
1
* x считать элемент
(u + v то из ( )3
.
2
и ( )
5
.
2
вытекает двусторонняя n n ),
2
оценка
1
− (v − u ≤ u + v − x ≤ v − u
n n )
1 ( n n ) * 1 ( n n ).
2
2
2
Из этой оценки, как правило, нетрудно получить оценку для норм разности
* x − v , . x* − u . n n
Основную трудность составляет отыскание начальных приближений u и
0 v . В [36] указан алгоритм отыскания таких начальных приближений.
0
Конечно, в различных частных случаях элементы u и v можно выбирать
0
0
более простым способом. Например, если f ∈ K , то в качестве u , конечно,
0
можно выбрать элемент f .
Пусть u и v удовлетворяют соответственно соотношениям ( )
2
.
2
и ( )
4
.
2
.
0
0
Будем считать дополнительно, что выполнены неравенства u − u ≥ p v − v ,
1
0
1 ( 0
1 ) v − v ≥ q u − u ,
0
1
1 ( 1
0 )
где одно из чисел p и q положительно (при p = q = 0 эти неравенства сов-
1
1
1
1
падают с ( )
2
.
2
и ( )
4
.
2
). Определим тогда элементы u + p v
(
)
6
.
2
*
1
1 1 u =
,
1
1+ p1 v + q u
( 7
.
2 )
*
1
1 1 v =
.
1
1+ q1
Справедлива следующая теорема [36]. Теорема 2.1. Справедливы соотношения
*
*
* u ≤ u ≤ x ≤ v ≤ v .
(
)
8
.
2
1
1
1
1
Формулы ( )
6
.
2
и ( 7
.
2 ) можно рассматривать как рекуррентный процесс
построения последовательностей * * u , v . Теорема 2.1 означает, что этот рекур- n n
17
рентный процесс сходится не медленнее последовательностей ( )
3
.
2
и ( )
5
.
2
, и
сохраняет монотонность последовательных приближений.
Многочисленные примеры показывают, что при достаточно общих усло-
виях процесс ( )
6
.
2
и ( 7
.
2 ) сходится существенно быстрее обычного метода
последовательных приближений.
Проиллюстрируем рассмотренный выше метод ускорения сходимости со-
ответствующими примерами. Пример 1. Пусть дано уравнения вида x = Ax + f , где
0 2
.
0.
3
9 A =
, f = .
0 4
.
0.
2
10
615384
.
19
*
Точное решение данного уравнения x =
, а спектральный ра-
307692
.
22
диус оператора A : r( ) A = 5464
.
0
.
1
Пусть z =
. Тогда искомые векторы u и v , согласно предложенному
0
1
0
0
выше алгоритму соответственно равны
25
−
25 u =
, v = .
0
25
−
0
25
Используя вышеизложенный метод, получим приближения u* и v* , между n n
которыми заключено решение исходного уравнения.
Соответствующие приближения u* и v* , к координатам вектора решения n n
представим в виде таблицы. Таблица 4 Приближения к 1-ой координате вектора решения
№, n
“ u*”
“ v* ” n n
1 17.776595
21.500000
2 19.124786
20.063157
3 19.575000
19.648888
18
5 19.590081
19.637779
10 19.614102
19.616522
12 19.615001
19.615724
13 19.615175
19.615570 Приближения к 2-ой координате вектора решения
1
20.531914
25.000000
2 21.685470
22.757894
3 22.270000
22.355555
5 22.278662
22.333750
10 22.306211
22.309005
12 22.307250
22.308084
13 22.307450
22.307906
Как видно из таблицы точность вычислений на 13 шаге составляет 10-3.
Отметим тот факт, что при отыскании решения данного уравнения методом
последовательных приближений (см.§1) для достижения такой точности по- требуется совершить 30 итераций. Пример 2. Пусть дано уравнение вида x = Ax + f , где
01
.
01
.
0 7
.
0 0
.
1
1
0 5
.
0 0
. 5 01
. 5 01
. 5
2 A =
, f =
.
0 2
.
0 7
.
0 0
. 2 0 0
. 8
3
08
.
0 2
.
0 3
.
0 3
.
4
Точное решение:
.
191
056645
.
194 439858 x* =
.
.
211151244
.
370
112372
Заметим, что спектральный радиус матрицы A : r( ) A = 9899
.
0
достаточно
близок к числу 1.
19
1
2
Пусть z = . Тогда искомые векторы u и v , согласно предложенному
0
3
0
0
4
алгоритму, соответственно равны:
−
255084
.
40286
255084
.
40286
−
407850
.
40814
407850
.
40814
u =
, v =
.
0
−
308750
.
44113
0
308750
.
44113
−
114187
.
76611
114187
.
76611
Используя вышеизложенный метод, получим приближения u* и v* , между n n
которыми заключено решение исходного уравнения.
Соответствующие приближения u* и v* , к координатам вектора решения n n
представим в виде таблицы. Таблица 5 Приближения к 1-ой координате вектора решения
№, n
20
800 190.659221
198.209034
1221 194.387724
194.491833
1500 194.436808
194.442897
2000 194.439839
194.439876 Приближения к 3-й координате вектора решения
1
-42673.917726 43987.251206
30 -10125.634450
10516.603526
400 -28.351559
449.928053
500 124.575055
297.464998
800 207.061821
215.228271
1221 211.094852
211.207464
1500 211.147945
211.154532
2000 211.151223
211.151264 Приближения к 4-ой координате вектора решения
1 -74917.128645
77220.207697
30 -17806.713604
18491.839792
400 -51.043768
789.991882
500 217.871592
521.891671
800 362.921284
377.281662
1221 370.013210
370.211233
1500 370.106572
370.118154
2000 370.112336
370.112408
Итак, на 2000 шаге точность вычислений составляет 10-4.
Рассмотренные выше примеры были реализованы при помощи, разрабо-
танной автором программы на языке программирования TURBO PASCAL.
21 §3. Метод однопараметрического итеративного агрегирования реше- ния линейных операторных уравнений вида x = Ax + f , где оператор A - матрица n - го порядка
В этом параграфе мы изложим еще один приближенный метод решения
систем алгебраических уравнений, позволяющий строить приближения к ре-
шению уравнений методом однопараметрического итеративного агрегирова-
ния. Соответствующий метод изложен в монографии [25] и является удоб-
ным и эффективным методом приближенного решения уравнений вида ( )
1
.
2
.
Рассмотрим уравнение вида ( )
1
.
2
x = Ax + f ,
где A - матрица порядка (n × n) , f - свободный вектор, n f ∈ R , x - неизвестный
вектор, n x ∈ R .
Предполагается, что f ≥ 0 и что спектральный радиус r( ) A матрицы A
меньше единицы: r( ) A < 1.
В этих условиях, как хорошо известно, уравнение ( )
1
.
2
имеет и притом
единственное неотрицательное решение
* x = x , к которому сходится обычный
метод последовательных приближений.
Если r( ) A не удовлетворяет данному условию, то широко известный ме-
тод последовательных приближений не позволяет построить приближения,
сходящиеся к точному решению * x уравнения (
)
1
.
2
. В такой ситуации важ-
ную роль приобретают другие численные методы решения уравнения вида
(
)
1
.
2
. К числу таких методов относят так называемые методы итеративного
агрегирования. По поводу которых, сразу можно отметить, что для их сходи-
мости совсем не обязательно выполнение условия r( ) A < 1 (т.е. методы итера-
тивного агрегирования сходятся в частных случаях, когда r( ) A > 1).
Ниже предлагается и исследуется способ, изложенный в [17], построения
приближений {x к решению * x , являющийся развитием метода итеративно- n }
го агрегирования в задачах математической экономики.
22
Рассмотрим скалярное уравнение t ⋅ l (x ) = t ⋅ l Ax + l f
)
1
.
3
(
0
0
0 (
0 )
0 (
),
где l - некоторый неотрицательный выбранный функционал агрегирования,
0
а x - выбранное начальное приближение к решению * x и пусть t = t(x - ре-
0 )
0
шение этого уравнения (если оно существует). Заметим, что для однозначной
разрешимости уравнения
)
1
.
3
(
достаточно выполнения условия
* A l ≤ α ⋅ l , α < 1.
)
2
.
3
(
0
0
Решение уравнения
)
1
.
3
(
, в случае если l x − l Ax ≠ выражается фор-
0 ( 0 )
0 (
) 0
0
мулой l ( f ) t(x ) l ( f )
0
=
0
=
.
0 l (x ) − l (Ax )
(
* l − A l )(x )
0
0
0
0
0
0
0
Определим теперь оператор F(x) равенством F(x) = t(x)⋅ Ax + f .
Имеют место следующие утверждения [17]. Лемма 3.1.Пусть выполнено условие
)
2
.
3
( . Тогда для каждого x > 0 определено значение оператора F(x) и для x > 0 выполняется неравенство F(x) ≥ f . Следствие.Если x > 0 , то определена последовательность {x n }:
0 x
= F x (n =
,
1
,
0
)
,...
2
)
3
.
3
(
n+
( ),
1 n причем x
≥ f . n 1
+
Всюду здесь предполагается выполненным условие
)
2
.
3
(
. Лемма 3.2.Функционал t(x) и оператор F(x) непрерывны в каждой точке x > 0 . Лемма 3.3.В области x ≥ f > 0 выполняется неравенство
23 t(x)
1
≤
.
1− α Лемма 3.4. Оператор F(x) удовлетворяет в области x ≥ f , x ≥ f усло-
1
2 вию Липшица: F(x ) − F(x ) ≤ [c +q] x − x ,
1
2
1 1 x1 1
1
2 1 где c1, q - const. Теорема 3.1.Пусть выполнено неравенство A
1 q =
< 1.
1− α Тогда последовательность
)
3
.
3
( сходится к решению * x уравнения (
)
1
.
2 при любом начальном приближении x ≥ f .
0
Рассмотрим соответствующие примеры. Пример 1. Рассмотрим систему вида ( )
1
.
2
, а именно x = Ax + f ,
где
0.01 0.1 0.15
1
A = 0.2 0.18 0.11 , f = 2 .
0.12 0.09 0.07
3
1.932344
Точное решение * x = 3.420915 .
3.806197
Спектральный радиус оператора A равен r( ) A = 3491
.
0
. В качестве началь-
ного приближения к вектору решения системы уравнений вида ( )
1
.
2
возьмем
3
вектор x =
. Полученные значения приближений по методу однопарамет-
0
3
3
рического итеративного агрегирования представим в виде таблицы. Таблица 6
№, n
Значения приближений x n
)
1
( x
(2) x
(3) x n n n
24
1 1.791878
3.492385
3.852792
2 1.947898
3.415026
3.801422
4 1.932529
3.420841
3.806139
8 1.932345
3.420915
3.806197
10 1.932344
3.420915
3.806197
12 1.932344
3.420915
3.806197
Как видно из таблицы уже на 12 шаге точность вычисления составляет
10-6.
Отметим также, что и в некоторых случаях когда r(A) > 1, метод однопара-
метрического итеративного агрегирования может «сходится» к решению
уравнения вида ( )
1
.
2
. Пример 2. Рассмотрим систему уравнений вида ( )
1
.
2
, где
1
.
0
2
.
0
1
.
0
3
.
0
4
.
0
1
2
.
0
3
.
0
4
.
0
5
.
0
3
.
0
2
A =
3
.
0
1
.
0
2
.
0
4
.
0
1
.
0 , f = 3.
1
.
0
1
.
0
4
.
0
1
.
0
2
.
0
4
2
.
0
4
.
0
1
.
0
1
.
0
1
.
0
5
−
645350
.
25
−
107519
.
39
Точное решение *
x = − 258140
.
22
.
−
519325
.
17
−
944249
.
21
Спектральный радиус оператора A равен r( ) A = 1256
.
1
. В качестве началь-
ного приближения к вектору решения системы уравнений вида ( )
1
.
2
возьмем
1
1
вектор
x =
. Полученные значения приближений по методу однопарамет-
0
1
2
3
рического итеративного агрегирования представим в виде таблицы. Таблица 7
№, n
Значения приближений x n
25
)
1
( x
(2) x
(3) x
(4) x
(5) x n n n n n
1
-24.384615 -30.307692
-16.615384 -12.153846 -8.846154
2
-25.930732 -43.561306
-27.143312 -19.443471 -27.233280
6
-25.626347 -39.062892
-22.240283 -17.472515 -21.900795
10 -25.645331 -39.107303
-22.257782 -17.519409 -21.943912
14 -25.645352 -39.107525
-22.258144 -17.519330 -21.944256
19 -25.645350 -39.107519
-22.258140 -17.519325 -21.944249
20 -25.645350 -39.107519
-22.258140 -17.519325 -21.944249
Как видно из таблицы 20 итераций метода однопараметрического итера-
тивного агрегирования дают точность вычислений при определении неиз-
вестного решения порядка 10-6.
По сравнению с предыдущим примером заметно снизилась скорость при-
ближения к решению уравнения вида ( )
1
.
2
(это связано с тем, что в этом
примере увеличилось значение r( ) A ).
Покажем на соответствующем примере, что приближения, полученные с
помощью метода однопараметрического итеративного агрегирования, могут
сходиться к решению уравнения вида ( )
1
.
2
и в том случае, когда спектраль-
ный радиус намного больше единицы. Пример 3. Рассмотрим систему уравнений вида ( )
1
.
2
, где
9
.
0
8
.
0
7
.
0
6
.
0
1
8
.
0
5
.
0
4
.
0
5
.
0
2 A =
, f =
.
81
.
0
6
.
0
7
.
0
4
.
0
3
6
.
0
2
.
0
51
.
0
42
.
0
4
− 692044
.
3
− 588537
.
1
Точное решение *
x =
.
− 316427
.
1
371875
.
1
Спектральный радиус оператора A равен r( ) A = 4409
.
2
. В качестве началь-
ного приближения к вектору решения системы уравнений вида ( )
1
.
2
возьмем
26
3
4
вектор
x =
. Полученные значения приближений по методу однопарамет-
0
4
4
рического итеративного агрегирования представим в виде таблицы. Таблица 8
№, n
Значения приближений x n
)
1
( x
(2) x
(3) x
(4) x n n n n
1 -4.648855
-2.071246 -1.697201 0.783715
2 -3.826261
-1.709944 -1.328899 1.247948
5 -3.694028
-1.590200 -1.316609 1.371591
9 -3.692045
-1.588538 -1.316427 1.371875
10 -3.692044
-1.588537 -1.316427 1.371875
11 -3.692044
-1.588537 -1.316427 1.371875
Как видно из таблицы на 11-м шаге точность вычисления достигается 10-6.
Отметим, что хорошо известный нам метод последовательных приближений
в этом случае не применим.
Рассмотренные выше примеры были реализованы с помощью разработан-
ной автором программе на языке программирования TURBO PASCAL.
Дальнейшим развитием метода однопараметрического итеративного агре-
гирования является так называемый метод многопараметрического итера-
тивного агрегирования [25]. Обратим внимание на то, что метод многопара-
метрического итеративного агрегирования обеспечивает, вообще говоря, бо-
лее высокую скорость сходимости приближений, по сравнению с однопара-
метрическим итеративным агрегированием, однако в нем на каждом шаге
приходится решать не одно уравнение с одним неизвестным, а систему из не-
скольких уравнений с соответствующим числом неизвестных. В этом случае
естественно “рисунок” метода усложняется, но при этом мы выигрываем в
скорости сходимости.
27 §4. Метод однопараметрического итеративного агрегирования реше- ния нелинейных операторных уравнений вида x = F(x) + f , где F(x) - не- линейный оператор.
Заметим, что метод однопараметрического итеративного агрегирования
применим также и для решения нелинейных систем алгебраических уравне-
ний.
Рассмотрим аналог метода итеративного агрегирования для случая нели-
нейных уравнений вида x = F(x) + f ,
(
)
1
.
4
с нелинейным оператором F(x) .
Примером таких уравнений может, например, служить следующая систе-
ма уравнений:
1
1
x = 01
. (x 5
) + 01
. (y 3
) + 1
1
y = 0 0
. x
1 + 0 2
. (y 3
) + 1
Если воспользоваться методом итеративного агрегирования (в его нели-
нейном варианте), изложенным в [67], т.е. перейти от уравнения ( )
1
.
4
к сле-
дующему уравнению: tl (x ) = tl F x
+ l f
0
0
0 [
( )
0 ]
( ),
0
где l - некоторый выбранный функционал агрегирования, а x - выбранное
0
0
начальное приближение, с неизвестной скалярной величиной t(x ) , а затем
0
определить значение t(x ) :
0 l ( f ) t(x )
0
=
,
0 l (x ) − l [F(x )]
0
0
0
0
при условии что l (x ) − l F x
≠ .
0
0
0 [
( )
0 ]
0
Тогда можно определить следующее приближение x по формуле:
1 def x = Φ(x ) = t(x ) ⋅ F(x ) + f .
1
0
0
0
Аналогично, по индукции положим: x
= Φ(x ) = t(x ) ⋅ F(x ) + f .
(
)
2
.
4
n 1
+ n n n
28
Последовательность ( )
2
.
4
определяет алгоритм метода итеративного агре-
гирования, в случае нелинейного операторного уравнения.
Пусть для любых x выполнено условие:
[c F(x) + q(t(y))]≤ q < ,1
(
)
3
.
4
1
где q таково, что выполнено F (x) − F (y) ≤ q x − y .
Теорема 4.1. Пусть выполнено условие ( )
3
.
4 . Тогда уравнение ( )
1
.
4 имеет и притом единственное решение * x , и к этому решению сходятся последова- тельные приближения ( )
2
.
4 .
Заметим, что в случае, когда F(x) - линейный оператор, этот метод совпа-
дает с изложенным в §3 методом итеративного агрегирования. Если же F(x) -
нелинейный оператор, то здесь фактически предлагается новый вариант ме-
тода, а именно нелинейный вариант метода итеративного агрегирования. В
работе [67] получены достаточные условия сходимости нелинейного вариан-
та метода итеративного агрегирования.
Рассмотрим примеры. Пример 1. Рассмотрим нелинейную систему вида
x = 0 0
. x
1 + 0 0
. 2y0 5. + 0 0
. z
1 0.25 + 3
y = 0 0
. x
3 0 5. + 0 0
. y
1 0.25 + 0. z
1 01. + 4
z = 00. x
1 0.25 + 0 2
. y0 5. + 0 4
. z0 5. +
5
Точное решение: x*=3.087732, y*=4.187488, z*=6.437405.
2
В качестве начального приближения выберем вектор x =
. Полученные
0
2
2
значения приближений представим в виде таблицы. Таблица 9
№, n
Значения приближений
x y z n n n
1 3.146834
4.394059
7.099478
29
2 3.083696
4.176646
6.397830
4 3.087717
4.187447
6.437256
6 3.087732
4.187488
6.437404
7 3.087732
4.187488
6.437404
Как видно из таблицы уже на 6-м шаге точность вычислений достигается
до 10-6.
При реализации метода итеративного агрегирования возможно появление
приближения, содержащего комплексные числа. В этом случае метод факти-
чески нереализуем.
Приведем пример соответствующий этому случаю. Пример 2. Рассмотрим нелинейную систему вида
x = 0 9
. x0 5. + 0 8
. y0.25 + 1
y = 0 7
. x0 5. + 0 9
. y + 1
3
В качестве начального приближения возьмем вектор x =
. Полученные
0
3
значения приближений представим в виде таблицы. Таблица 10
№, n
Значения приближений
1 -8.965667
-13.928957
2
комплексное число
комплексное число
Как видно из таблицы на 2-м шаге вычислений появляются комплексные
числа. Предложенный метод на данном примере нереализуем.
При реализации метода итеративного агрегирования возможны, также, та-
кие случаи, когда на нечетном шаге наблюдается приближение “снизу” к
вектору решения, а на четном шаге наблюдается приближение “сверху” к
вектору решения.
Приведем пример соответствующий этому случаю. Пример 3. Рассмотрим нелинейную систему вида
x = 5
.
0 x +
(
5
.
0 y)0,5 +1
y = 9
.
0
0 5
. x +1
30
3
В качестве начального приближения возьмем вектор x =
. Полученные
0
3
значения приближений представим в виде таблицы. Таблица 11
№, n
Значения приближений
x y n n
1 3.280364
2.502408
2 3.824302
2.893678
6 3.699622
2.764530
7 3.613336
2.687309
12 3.655982
2.725457
24 3.649138
2.719333
25 3.648906
2.719125
30 3.649022
2.719229
31 3.648990
2.719200
Точное решение данной системы уравнений: x=3.649003 и y=2.719212.
Как видно из таблицы на 30-м шаге наблюдается сходимость к решению до
4-го знака.
Интересно отметить, что в процессе реализации предложенного метода
итеративного агрегирования возможна такая ситуация, когда на первый
взгляд метод сходится, однако наблюдается сходимость к вектору, не яв-
ляющемуся решением системы.
Приведем соответствующий пример. Пример 4. Рассмотрим нелинейную систему вида
x =|y|0.5+ .
0 |
2 z|0.5+1
y = . |
01 x|0.5+ .
0 |
3 y|0.3+ .
0 |
5 z +
| 2
z =|x|0.25+ .0 |5y+| |5z|0.5+
3
31
В качестве начального приближения к вектору решения возьмем вектор
1
x =
. Полученные приближения представим в виде таблицы.
0
2
3 Таблица 12
№, n
Значения приближений
x y z n n n
1 -0.259054
0.591686 -4.623341
2 0.637854
1.209162 -0.551321
6 0.210033
1.314923 -1.283281
24 0.151685 1.328081 -1.479733
30 0.151675 1.328082 -1.479756
31 0.151675 1.328082 -1.479758
После соответствующей проверки замечаем что вектор, к которому схо-
дятся значения приближений по методу однопараметрического итеративного
агрегирования не является решением данной системы уравнений. Из этого
следует, что сам факт сходимости еще не гарантирует, что значения прибли-
жений сходятся именно к решению данной системы уравнений.
Рассмотренные выше примеры были реализованы при помощи разрабо-
танной автором программы на языке программирования TURBO PASCAL.
32 ГЛАВА 2. АЛГОРИТМЫ ПОСТРОЕНИЯ ПРИБЛИЖЕНИЙ, СХОДЯЩИХСЯ К СПЕКТРАЛЬНОМУ РАДИУСУ И СОБСТВЕННОМУ ВЕКТОРУ ЛИНЕЙНОГО ОПЕРАТОРА §5. Построение приближений, сходящихся к спектральному радиусу линейного оператора
Знание нормы оператора, а точнее говоря информации о том, что норма
оператора меньше единицы, позволяет строить приближение к решению
уравнения с этим оператором. Однако, величина нормы оператора сущест-
венно зависит от того, каким образом введена норма в соответствующим
пространстве. Один и тот же оператор может иметь разные нормы, в зависи-
мости от способа введения нормы в пространстве, при этом не исключено,
что одна норма будет меньше единицы, а другая больше единицы. Поэтому
возникает принципиальный вопрос о том, в каких случаях можно гарантиро-
вать существование эквивалентной нормы [36] в пространстве, в которой
норма оператора будет меньше единицы.
В силу неоднозначности введения нормы в пространстве, возникает необ-
ходимость иметь какую-нибудь общую характеристику, знание которой бу-
дет давать информацию о сходимости итерационного процесса к точному
решению операторного уравнения. Одной из таких характеристик является
спектральный радиус оператора A , который тесно связан с понятием спектра
оператора A [36]. Часть предыдущего материала, а также и дальнейшее из-
ложение материала тесно связано с понятием спектрального радиуса опера-
тора A [36].
Пусть A - линейный оператор в n-мерном пространстве n E . Число λ на-
зывается собственным значением оператора A , если уравнение Ax = λx
имеет ненулевое решение. Совокупность всех собственных значений называ-
ется спектром оператора A , а все остальные значения λ называются регу-
лярными значениями оператора A . Иначе говоря, λ есть регулярное значе-
33
ние, если оператор (A − λI ) имеет ограниченный обратный оператор. В конеч-
номерном пространстве возможны два случая:
1) уравнение Ax = λx имеет ненулевое решение, т.е. λ есть собственное
значение для A , оператора (A λ ) 1−
− I при этом не существует;
2) существует ограниченный оператор (A λ ) 1−
− I , т.е. λ есть регулярная
точка. Определение 5.1.Пусть λ - собственное значение оператора A . По- A ложим r(A) = sup λ A величина r(A) - называется спектральным радиусом оператора A .
Сразу отметим следующий очевидный результат [36]: если у оператора A
есть собственное значение λ , такое что λ > 1, то при любой эквивалентной
нормировке пространства норма оператора больше единицы.
Выше уже отмечалось, что для существования у системы уравнений ( )
1
.
2
неотрицательного решения *
* x = x ( f ) для заданного неотрицательного векто-
ра f достаточно, чтобы выполнялось неравенство: r( ) A < ,
1
где r( ) A - спектральный радиус матрицы А. В этой связи отметим следую-
щую теорему [4]. Теорема 5.1.Пусть A - линейный оператор, действующий в банаховом пространстве Е, r( ) A - спектральный радиус оператора A , ε>0 - произволь- но заданное число. Тогда в пространстве Е можно ввести новую норму x ,
ε эквивалентную заданной норме пространства Е и такую, что будет выпол- няться неравенство: A ≤ r( ) A + ε . Следствие.Для существования в пространстве Е по отношению к за- данному оператору A - эквивалентной нормы, такой, что выполняется не- равенство:
34 A < 1 достаточно, чтобы выполнялось неравенство r( ) A < 1.
Это следствие позволяет ответить на вопрос, в каких случаях можно рас-
считывать на то, чтобы оператор A был оператором сжатия. Тем самым во-
прос о том, существует ли такая эквивалентная норма, в которой будет опе-
ратор A - оператором сжатия сводится к вопросу об оценке сверху спек-
трального радиуса r( ) A - этого оператора.
Отметим, что проблеме оценок спектрального радиуса оператора r( ) A как
сверху, так и снизу, посвящены многочисленные результаты [34], [36], [38],
[39],[66].
В этой связи важную роль играют двусторонние оценки для значений
спектрального радиуса r( ) A линейного положительного оператора A .
Для получения этих оценок можно воспользоваться следующими резуль-
татами [36]. Теорема 5.2.Пусть n u ∈ R - вектор у которого все компоненты u
( )
0
0 i (i=1,2,..n) являются положительными числами: (u ) > 0 . Пусть α ≥ 0 и β ≥ 0
0 i таковы, что
αu ≤ Au ≤ βu
0
0
0 (здесь и далее запись x ≥ y , n x, y ∈ R означает, что для всех i = ,
1 n выполня- ются неравенства (x) ≥ (y) ). Тогда α ≤ r( ) A ≤ β . i i При этом если α , β соответственно таковы, что n n
α = max α α ≤
, n
{ : u Anu
0
0}
β = min β
≤ β
n
{ : Anu u
0
0 }, то
1 / n
1 / n
α
≤ r(A) ≤ β n n и при этом последовательности { 1/ n
α и { 1/ n
β сходятся, соответственно n
} n
} монотонно возрастая и монотонно убывая, к r( ) A .
35
На этом результате базируется следующий алгоритм построения моно-
тонно сходящихся приближений к величине r( ) A , который в подробной запи-
си имеет следующий вид.
Пусть α иβ определяются формулами n n n
( A u ) n
(A u )
0 i
α = min
;
0 i
β = max
. n n i =1,n
(u ) i ,
1
= n u
( )
0 i
0 i Замечание.Как следствие из работ Красносельского М.А., Стеценко В.Я. и др. [34], [36], [38], [39], [66], можно установить, что некоторые под- последовательности этих последовательностей являются сходящимися, причем их предел равен r( ) A . Тем самым построение этих последовательно- стей можно использовать для вычисления спектрального радиуса операто- ра A .
Далее запись 1/ n
α
↑ r( ) A означает факт монотонной сходимости “снизу” n
последовательности { 1/ n
α } к спектральному радиусу r( ) A , а 1/ n
β
↓ r( ) A - факт n n
монотонной сходимости последовательности { 1/ n
β } “сверху” к числу r( ) A . n
С помощью разности β1/n -α1/n можно контролировать степень близости n n
соответствующих последовательностей к величине r( ) A .
По предложенному в теореме 5.2 алгоритму автором была разработана со-
ответствующая программа на языке программирования TURBO PASCAL. Пример 1. Пусть
1
.
0
1
.
0
1
.
0
3
.
0
2
.
0
1
2
.
0
3
.
0
2
.
0
1
.
0
5
.
0
1
A =
1
.
0
1
.
0
1
.
0
2
.
0
3
.
0 , u = .
0
1
2
.
0
6
.
0
6
.
0
1
.
0
5
.
0
1
6
.
0
1
.
0
3
.
0
2
.
0
4
.
0
1
Используя вышеизложенный алгоритм, найдем приближения (соответст-
венно снизу и сверху) к спектральному радиусу матрицы A . Вычисления
представим в виде таблицы.
36 Таблица 13
№ п/п, n
1 / n
α
↑ r( ) A
1 / n
β
↓ r( ) A n n
1 0.800000
2.000000
2 1.081665
1.555634
3 1.134447
1.466982
4 1.172925
1.418077
8 1.228434
1.351138
16 1.257382
1.318685
32 1.272111
1.302752
64 1.279540
1.294858
Как можно заметить из таблицы, на уже на 64-м шаге значение спек-
трального радиуса данной матрицы A заключено между 1.279540 и 1.294858.
Точное значение спектрального радиуса данной матрицы равно 1.287012.
Этот алгоритм в аналогичной форме приемлем для получения оценок сни-
зу, соответственно сверху для спектрального радиуса интегрального опера-
тора вида Ax (t ) = ∫ K (t, s) x(s)ds
)
1
.
5
(
Ω
с неотрицательным непрерывным ядром K(t,s) .
В этом случае последовательности имеют вид K (t , s)u (s)ds
∫ K (t ,s)u (s)ds
∫ n
0 n
0
α = min Ω
, β = max Ω
, n n t ∈Ω u (t ) t ∈Ω u (t )
0
0
где K (t,s) - n -ое итерированное ядро, а u (t) - непрерывная и положительная n
0
на Ω функция.
Отметим, что скорость сходимости последовательностей α1/n и β1/n к ве- n n
личине спектрального радиуса
1 r( ) A имеет порядок O n .
В связи с вышеизложенными результатами выясняется актуальность оце-
нок спектрального радиуса r( ) A оператора A как в случае когда A – это
37
квадратная (n × n) матрица, так и в случае, когда A - интегральный оператор
вида
)
1
.
5
(
.
Важную роль в теории для справедливости принципа Хикса в случае ин-
тегрального уравнения с неотрицательным ядром играет условие вида r( ) A < 1,
)
2
.
5
(
где r( ) A - спектральный радиус интегрального оператора A с ядром K (t, s) .
Естественно иметь признаки, обеспечивающие выполнение условия
)
2
.
5
(
.
Необходимо получить соответствующие признаки для случаев, когда A :
10) A = (a ) (i, j = ,1n); ij
20) A - интегральный оператор вида
)
1
.
5
(
, в котором Ω - ограниченное
замкнутое множество из евклидова пространства m R , K (t, s) - функция, для
которой при некоторых p p > 1 и q =
выполняется условие: p − 1
1
q
|K(t,s)|q ds dt
∫ ∫
< +∞ .
)
3
.
5
(
Ω Ω
При выполнении условия
)
3
.
5
(
оператор
)
1
.
5
(
, как известно, действует в
пространстве L (Ω) и является вполне непрерывным оператором в этом про- p
странстве [66].
Соответствующие признаки для случая 10) были получены в работах Сте-
ценко В.Я.
Получим соответствующие признаки для случая 20).
Предварительно напомним определение неразложимости оператора. По-
ложительный линейный оператор A назовем неразложимым, если из того, что x > θ , x ≥ αAx (α > 0), следует, что x >> θ .
Введем в рассмотрение следующие функции P(t) = |K(t,s)|ds
∫
, Q(t) = |K(s,t)|ds
∫
.
38 Pα (t) 1− Q α (t) ≤ 1, (t ∈ Ω)
)
4
.
5
( и, кроме того, выполняется одно из двух следующих условий: 10) в неравенстве
)
4
.
5
( равенство допускается лишь на множестве точек лебеговой меры нуль; 20) в неравенстве
)
4
.
5
( строгое неравенство выполняется для всех t из некоторого множества ω ∈ Ω ,
ω mes > 0 , оператор A - неразложим в про- странстве L (Ω . p
) Тогда спектральный радиус r( ) A интегрального оператора A
)
1
.
5
( в про- странстве 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 = θ
λ A , а, следовательно, и r( )
λ A
0
и r(A ) = 0 , то для всех достаточно малых λ > 0 выполнено неравенство
0 r( ) < .
1
λ A
Возможны два случая:
1) r(A ) < 1;
1
2) r(A ) ≥ 1.
1
39
В первом случае теорема доказана, так как A = A . Во втором случае най-
1
дется хотя бы одно значение λ = λ ∈ ( ]
1
;
0 , для которого r( A ) = 1. В этом слу-
0
λ 0
чае r(A ) = является собственным значением оператора
, которому отве-
λ
1 Aλ
0
0
чает неотрицательная собственная функция x (t) ∈ L (Ω):
0 p A x (t) = x (t),
λ
0
0
0
откуда в силу
)
4
.
5
(
∫
α
1− K (t, s)x (s)ds ≥ P (t)Q α (t)x (t) ,
)
5
.
5
(
λ
0
0
0
Ω
где K (t,s) = λ K(t,s
λ
).
0
0
Установим, что в неравенстве
)
5
.
5
(
знак строгого неравенства имеет место
на некотором множестве ω : ω ∈ ,
Ω
ω mes
> 0 для каждого из случаев 10), 20).
1
1
1
При условии 10) это утверждение очевидно.
При условии 20) утверждение следует из того, что неотрицательная собст-
венная функция положительного неразложимого оператора в пространстве L (Ω , как квазивнутренний элемент конуса K неотрицательных функций p
)
пространства L (Ω , почти всюду в Ω принимает положительные значения. p
)
Замечая, что K (t,s) = Kα (t,s) ⋅ K1−α (t,s
λ
λ
λ
)
0
0
0
и применяя к левой части в
)
5
.
5
(
неравенство Гельдера с показателями
1 p = 1 , q =
,
α
1 − α
получим
1
1 p q
K (t,s)ds K (t,s)xq (s)ds ≥ x (t) ≥ Pα (t)Q1−α (t)x (t
∫
λ
∫ λ
).
0
0
0
0
0
Ω
Ω
Так как при этом K (t,s) ≤ K(t,s
λ
),
0
то
Ω
Ω
причем здесь строгое неравенство выполняется для всех t ∈ω , где ω ∈ Ω и
1
1
ω mes
> 0 .
1
Нетрудно видеть, что для всех t ∈ Ω , для которых x (t) > 0 выполняется
0
также неравенство: P(t) > 0 .
Действительно, если для некоторого множества ω , ω ∈ Ω ,
1
1 P(t) = 0 (t ∈ ω ) ,
1
то в силу неотрицательности K(t,s) это означает, что для t ∈ω , функция
1 K (t, s) как функция аргумента s на Ω эквивалентна нулю для всех t ∈ ω . То-
1
гда эквивалентна нулю для всех t ∈ω на множестве Ω и функция K(t,s)x (s)
1
0
и поэтому для t ∈ω
1 x (t) = λ K(t,s)x (s)ds = 0,
0
0 ∫
0
Ω
т.е. x (t) ≡ 0для t ∈ω .
0
1
Сказанное означает, что из неравенства
)
6
.
5
(
следует неравенство
1
−α
7
.
5
(
)
K t s xq
( , ) (s)ds
≥ Q1−α (t)x (t),
∫
0
0
Ω
причем в
7
.
5
(
) знак строгого неравенства имеет место по крайней мере для t ∈ ω . Извлекая из обеих частей неравенства
7
.
5
(
) корень степени 1
( − α ) , а за-
1
тем, интегрируя по t на множестве Ω , получим
∫dt∫K(t,s)xq(s)ds > Q t xq t dt
0
∫ ( ) ( ) .
0
Ω
Ω
Ω
Меняя в левой части порядок интегрирования, найдем что Q t xq t dt > Q t xq
( ) ( )
( ) (t)dt.
∫
41
Аналогичный результат имеет место и в том случае, когда интегральный
оператор Ax t
( ) = ∫ K t(,s)x(s)ds
Ω
действует в пространстве С(Ω) и неразложим в этом пространстве относи-
тельно конуса неотрицательных функций пространства С(Ω) . §6. Построение приближений, сходящихся к собственному вектору ли- нейного оператора
Большое количество работ Крейна М.Г., Красносельского М.А., Стеценко
В.Я. и др. посвящено проблеме отыскания собственных векторов как линей-
ных, так и нелинейных операторов. В случае нелинейных операторных урав-
нений, проблема отыскания собственных векторов и собственных значений
нелинейных операторов является существенно более сложной. В этом пара-
графе рассматривается задача на построение приближений к собственным
значениям, собственным векторам, т.е. построение приближений к таким
λ, x ∈ E , что
λx = F(x) ,
(
)
1
.
6
где F(x) - линейный или нелинейный оператор, действующий в банаховом
пространстве E . По аналогии с предыдущим материалом будем считать, что
пространство E полуупорядоченно с помощью конуса Крейна K [36]. Пред-
положим, что оператор F(x) положительный, т.е для x
∀ ∈ K следует, что F(x) ∈ K . При дополнительных предположениях относительно оператора F(x) , уравнение (
)
1
.
6
имеет для некоторого значения λ = λ решение
0
* x = x (λ ) , принадлежащее K . Соответствующий вектор x естественно на-
0
0
0
звать собственным вектором оператора F(x) , отвечающим собственному зна-
чению λ . Точное значение собственного вектора может быть найдено лишь
0
в весьма частных случаях, поэтому возникает задача о построении прибли-
жений к собственному вектору, с заданной степенью точности. При этом
42
особый интерес представляют методы позволяющие строить такие прибли-
жения u ,v к собственному вектору * x , которые удовлетворяют условию n n u ≤ x* ≤ v
n n
и при этом * x − u → 0 ,* x − v → 0 . n n
В этом случае, естественно, называть элементы u и v как приближения к n n
собственному вектору * x по недостатку и соответственно по избытку. Пред-
ложим соответствующие способы построения собственных векторов и собст-
венных значений для некоторых классов линейных операторов.
Рассмотрим вначале случай линейного положительного оператора. Его, в
отличие от случая нелинейного оператора, привычнее обозначать не буквой F , а буквой A . Уравнение (
)
1
.
6
в этом случае перепишется в виде
λx = Ax .
Элементы x, y ∈ K называются эквивалентными, если tx ≥ y и ty ≥ x при
некотором t > 0 . Конус K распадается на классы попарно эквивалентных
элементов – компоненты эквивалентности. Для эквивалентных элементов x, y ∈ K определена величина
θ (
inf :
≥ x, y)
{t tx y}
=
{
.
sup t : tx ≤ } y
Оператор A будем предполагать не только положительным, но и фокуси-
рующим. Напомним определение фокусирующего оператора [36]. Определение 6.1.Оператор A называется фокусирующим на конусе K , если он u -положительный и если для всех x > θ, y > θ существует постоян-
0 ная κ 2 , такая что
2
θ ( , Ax Ay) ≤ κ . При этом число κ назовем постоянной фокусирования [38].
Приведем критерий фокусирования. Утверждение 6.1.Для того чтобы положительный оператор A был фо- кусирующим, необходимо и достаточно, чтобы существовали такие u ∈ K ,
0
ρ − const , что для каждого x ∈ K выполняется неравенство
43
λ(x)u ≤ Ax ≤ ρλ(x)u .
(
)
2
.
6
0
0 Здесь u - фиксированный элемент конуса K . Это утверждение означает,
0 что AK ⊂ K . u ,ρ
0
Примерами фокусирующих операторов являются матрицы с положитель-
ными элементами. Лемма 6.1.Пусть x > θ , y > θ и x ≤ ay, y ≤ bx ,
(
)
4
.
6 причем
||x|| =||y|| = 1 .
(
)
5
.
6 u u
0
0 Тогда функционал δ (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 ∈K [36]: u0
δ
κ − 1
( Ax, Ay) =
δ (x,y) ,
κ + 1 т.е. в полуметрике δ (x, y) фокусирующий оператор является оператором сжатия на множестве K с постоянной q : u0
κ − 1
( 7
.
6 ) q ≤
< 1.
κ + 1
В случае, когда A - матрица с положительными элементами, постоянная
фокусирования определяется следующей теоремой [38]. Теорема 6.2.Константа фокусирования относительно конуса n K ⊂ R
+ линейного оператора А порожденного матрицей A с положительными эле- ментами aij определяется равенством a a
κ (A,K ) = max ip jq .
+ i, j, p,q a a jp iq
Для всех x ∈K определим оператор ˆA : u0
44
ˆ Ax x A =
.
|| Ax ||u0
Оператор Aˆ
рассмотрим
на
множестве E = K ∩ S ,
где
1 u
1
0 S =
: ∈
,| | = 1 . Полуметрика δ (x, y) , рассматриваемая на E , является
1
{x x E x u u
0
0
}
1
метрикой. В самом деле, из равенства δ (x, y) = 0 (x, y ∈ E ) следует, что x = y
µ ,
1
µ > 0 , но так как
||x|| =||y|| = 1 , u u
0
0
то µ = ,
1 т.е. x = y . Оператор Aˆ является на E оператором сжатия этого мет-
1
рического пространства, последний факт доказан в [38]. В силу сказанного Aˆ имеет в E единственную неподвижную точку * x :
1
*
*
ˆ x A = x
т.е. Ax* = Ax* x*
||
||
u0
и к * x сходится метод последовательных приближений x
ˆ
= x A , (n =
,
1
,
0
,...)
2
n+1 n
при любом начальном приближении x ∈K ,x ≠ θ .
0 u
0
0
При этом на основании утверждения принципа сжатых отображений име-
ет место следующая оценка близости x к * x : n qn
(
)
8
.
6
δ ( * x , x ) ≤
δ (x , x ) . n
1
1
0
− q
Здесь δ (x, y) определяется следующим образом. Пусть x ≤ t y, y ≤ t x , то-
1
2
гда δ (x, y) = ln max(t ,t ) .
1
2
Тем самым установлена справедливость следующей теоремы. Теорема 6.3.Пусть A - фокусирующий оператор с постоянной κ .Тогда A имеет в K собственный вектор * x , которому отвечает собственное u0 значение λ . К этому вектору * x сходится метод
1 Ax x n
= (n =
,
1
,
0
,...)
2 n+1
|| Ax || n u0
45 при любом x ∈K ,x ≠ θ . При этом справедлива оценка близости ( )
8
.
6 , где q
0 u
0
0 удовлетворяет неравенству ( 7
.
6 ) . К собственному вектору * x также схо- дятся последовательности u и v , которые удовлетворяют следующему n n неравенству u ≤ x* ≤ v n n где
κ 1
− κ 1 n
−
a
⋅
2
κ +1
ˆ u = Anx , n
0
b
(
)
9
.
6
κ 1
− κ 1 n
−
b
⋅
2
κ +1
ˆ v = Anx , n
0
a
(
)
10
.
6 а постоянные a и b таковы, что ax ≤ Ax ≤ bx .
0
0
0
Ясно, что коэффициенты в правой части ( )
9
.
6
и (
)
10
.
6
при n → ∞ стре-
мятся к единице. Как уже отмечалось в последней теореме последователь-
ность ˆAnx сходится к собственному вектору * x , в силу чего u и v сходятся
0 n n
к * x по норме пространства Е.
Итак, мы получили возможность строить последовательности u и v , схо- n n
дящиеся к * x , при этом u сходится по норме пространства E снизу, а v - n n
сверху.
Если теперь вместо оператора A взять сопряженный оператор * A , то учи-
тывая, что этот оператор является положительным в * E относительно полу-
группы * K , мы аналогичным образом получим способ построения прибли-
жений l(n) l(n)
,
, к собственному функционалу *l оператора * A :
1
2
(n)
*
(n) l
≤ l ≤ l .
1
2
С помощью этих последовательностей мы на основании l (v )
λ − r( )
0
0 A =
0 l (u )
0
0
можем утверждать, что
46
(n) l (v )
(n) l (v )
1
0
λ −
≤ r( )
2
0 A ≤ λ +
,
0
(n) l (u )
0
(n) l (u )
2
0
1
0
а это позволяет строить две последовательности, сходящиеся к r( ) A , соответ-
ственно, снизу и сверху, тем самым с любой точностью находить значение
спектрального радиуса r( ) A оператора A .
Проиллюстрируем эти результаты соответствующими примерами. Пример 1. Пусть
1
3
1
1 A =
, u = , x = .
2
1
0
1
0
1
В данном примере точное значение собственного вектора, отвечающего
1
ведущему собственному значению λ :x* =
.
1
.
0
816
Выберем в данном примере n=7. Используя метод, описанный в теореме
6.3 получим приближения к соответствующим координатам собственного
вектора * x . Представим эти приближения в виде следующей таблицы. Таблица 14
№ п/п,
Приближения к координатам вектора * x n
x1 x2
1 1
0.750000
2 1
0.846154
3 1
0.804348
4 1
0.821656
5 1
0.814338
6 1
0.817405
7 1
0.816115
Теперь, на основании теоремы 6.3, получим приближения к соответст-
вующим координатам собственного вектора * x “снизу” и “сверху”. В данном
примере a=3, b=4, κ=2.449. Эти приближения также представим в виде таб-
лицы.
47 Таблица 15
№ п/п, n u v n n
1
0 91612
.
109156
.
0 68709
.
081867
.
2
0 96385
.
103750
.
081557
.
087789
.
3
0 98465
.
101559
.
0 79200
.
081689
.
4
0 99352
.
10
. 0652
081633
.
082701
.
5
0 99727
.
100274
.
081212
.
081657
.
6
0 99885
.
100115
.
081647
.
081834
.
7
0 99952
.
100048
.
081572
.
081651
.
Используя формулу ( )
8
.
6
, оценим в какой близости от точного решения * x
на 7-м шаге мы находимся: δ (x , * x ) = 00114
.
0
.
7
В приведенном примере приближение T x =
)
1
;
1
(
случайно оказалось доста-
0
точно близким от * x в метрике δ (x, y) :
δ (x , * x ) = 49617
.
0 .
0
Возьмем теперь начальное приближение T x = ;
1
( )
4 , сильнее отклоняющее-
0
ся от * x :
δ (x , * x ) = 72455
.
3 .
0
В этом случае получим последовательно
)
46
.
0
;
1
( T x =
, x = (
)
1
;
97
.
0 T ≈ x .
1
2
0
Отметим, что для получения приближения с той же точностью, что и при
выборе T x =
)
1
;
1
(
нам понадобится в этом новом случае всего на две итерации
0
больше, чем в предыдущем случае, т.е. пример говорит о том, что данный
метод не очень “чувствителен” к выбору начального приближения x .
0
50
7
0 32814
.
0 71184
.
0 47071
.
1 02113
.
0 31699
.
0 68766
.
0 67895
.
147287
.
0 53534
.
116134
.
8
0 36654
.
0 63732
.
0 52577
.
0 91418
.
0 35408
.
0 61565
.
0 75837
.
131861
.
0 59796
.
103969
.
9
0 39668
.
058890
.
0 56900
.
0 84472
.
0 38319
.
056887
.
082073
.
121842
.
0 64713
.
0 96070
.
10
0 41972
.
055658
.
0 60205
.
0 79836
.
0 40544
.
053765
.
086839
.
115155
.
0 68471
.
0 90798
.
Ниже предлагаются два алгоритма построения собственных векторов * x и
* l операторов A и * A , соответствующего значению λ .
1
Пусть A - неразложимый вполне непрерывный положительный оператор, u - фиксированный внутренний элемент K , α и β - последовательности
0 n n
такие, что
α = inf
, n
{α : Anu ≤ αu ,u >>θ
0
0
0
}
β =
. n
{
sup β : Anu ≥ βu ,u >> θ
0
0
0
}
Построим последовательности:
1
2
1
1−
1− n−2 n 1 u n
= β u n
+ β Au + ... n
+ β A u + A − u , n n
0 n
0 n
0
0
1
2
1
1−
1− n−2 n 1 v n
= α u n
+ α Au + ... n
+ α A u + A − u . n n
0 n
0 n
0
0
Тогда согласно результатам [66] последовательности
51 u v n A
, n A Au Av n n
сходятся к единственному нормированному вектору оператора 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 = λ , (λ ∈σ ( ) A ).
1
Для различных классов положительных операторов (сильно положитель-
ные, u - положительные, фокусирующие, острые [36,38,69]) гарантировано
0
строгое неравенство
λ < r( ) A (λ ∈σ ( ), A λ ≠ λ .
(
)
11
.
6
1 )
Дополнительно предположим, что E = H - гильбертово пространство, A -
самосопряженный положительный оператор, то есть A* = A.
Пусть y ∈ K, y ≠ θ,l ∈ * K ,l ≠ θ . Положим
0
0
0
0 l (Ay )
0
0
τ =
1 l ( y )
0
0
и определим элементы l = y = τ Ay , l = y = τ Ay .
1
1
1
0
2
2
2
1
Вообще, пусть уже определены τ , y ,l . Положим n 1
− n 1
− n 1
−
52 l (Ay ) n 1
− n 1
−
τ =
, l = y = τ Ay . n l ( y ) n n n n 1
− n 1
− n 1
−
Для определенности последовательностей {τ , y , l необходимо и доста- n } { n } { n }
точно выполнения условия l (y ) ≠ 0 для любого n . Для этого, например, дос- n n
таточно, чтобы оператор A был неразложимым [36]. Наряду с последова-
тельностью {y образуем последовательность n } x = ϕ = An y (n = ,
1 ,...)
2
. n n
0
Ясно, что для каждого n l = τ x = τ ϕ , l = y = τ ⋅τ x = τ ⋅τ ϕ
2
2
( 2 1) 2 ( 2 1) ,...,
1
1 1
1 1
2 n n
l = y = ∏τ x = ∏τ ϕ . n n
i n
i n
i 1=
i 1=
Поэтому l (Ay ) ϕ
( Ax ) n 1
− n 1
−
τ =
= n−1 n−1 . n l ( y )
ϕ (x ) n 1
− n 1
− n−1 n−1
Положим x
ϕ
)
1
( n n
)
1
( x
=
=
= ϕ , n n x
ϕ n n
тогда, как легко видеть, имеет место неравенство
)
1
(
ϕ (
)
1
( Ax )
(
)
12
.
6
n 1
− n 1
−
τ =
(n = ,
1 ,...)
2
. n
)
1
(
ϕ ( )1
( x ) n 1
− n 1
−
В силу (
)
11
.
6
последовательности { )1( x
= ϕ
сходятся к собственному n }
{ )1(n}
вектору *
* x = ϕ оператора
* A = A , и поэтому в силу (
)
12
.
6
последовательность
{τ сходится к числу n }
*
ϕ ( * Ax )
λ =
.
1
*
ϕ ( * x )
Аналогичным свойством сходимости к λ обладает последовательность
1 l (Ay )
0 n 1
− t =
, n l ( y )
0 n 1
−
53
λ n
при этом разность t − λ имеет порядок Ο
2
. Оказывается , что после- n
1
λ
1
довательность {τ имеет более высокую скорость сходимости, а именно n }
2
n
λ
2
τ − λ = Ο
.
n
1
λ
1
Естественно теперь распространить этот метод на операторы, действую-
щие в банаховом пространстве E с конусом K . Исходя из y ∈ K, y ≠ θ ,
* l ∈ K ,l ≠ θ , положим
0
0
0
0 l (Ay ) n 1
− n 1
−
τ =
, (n = ,
1 ,...)
2
n l ( y ) n 1
− n 1
−
где
* l = τ A l , y = τ Ay (n = ,
1 ,...)
2
. n n n 1
− n n n 1
−
Пусть * * x ,l - собственные векторы операторов
*
, A A , соответственно,
*
*
* x ∈ K,l ∈ K такие, что x* = l* =1. Тогда имеют место асимптотические
оценки
2
n
λ
2
τ − λ = Ο
, n
1
λ
1
λ n
* ln
−
= Ο
2
.
* y
x n
−
, l y l
λ n n
1
В отличие от самосопряженного оператора здесь, хотя объем работы воз-
растает в два раза, мы получаем приближения не только к собственному зна-
чению λ и собственному вектору * x оператора A , но и к собственному век-
1
тору *l сопряженного оператора * A .
По предложенным выше алгоритмам, автором были составлены про-
граммы на языке программирования TURBO PASCAL.
Выше оператор A предполагался линейным. Построим приближения к
собственному вектору * x для некоторых классов нелинейных операторов F(x) . Выделим соответствующий класс нелинейных операторов F(x) , дейст-
54
вующих в полуупорядоченном банаховом пространстве, являющимися моно-
тонными относительно нормального конуса K и такими, что F(αx)
µ
≤ α F(x)
для всех x ∈ K и α ∈ [ ;
1 +∞], где µ < ,
1 µ − const .
Если в полуупорядоченном банаховом пространстве E с конусом K вве-
сти следующую метрику: для двух элементов x, y ∈ K таких, что x ≤ λy, y ≤ x
µ
(
)
13
.
6
положить d(x, y) = ln
{
max λ , µ
0
0},
где λ ,µ , соответственно, точные нижние и верхние границы всех чисел λ,µ
0
0
для которых выполняются неравенства (
)
13
.
6
, то, во-первых, d(x, y) удовле-
творяет всем аксиомам метрики и во-вторых, для нормального конуса K вся-
кая компонента связности C конуса K становится полным метрическим про- k
странством в метрике d(x, y) , а оператор F(x) является оператором сжатия
соответствующей компоненты связности. При этом собственные векторы
оператора F(x) из конуса K являются неподвижными точками оператора
1 F(x), а каждая фундаментальная по метрике d(x, y) последовательность
λ
элементов {x является фундаментальной и по норме пространства E и на- n }
оборот. При этом пределы последовательностей {x по норме пространства n } E и по метрике d(x, y) совпадают.
Из этого в силу принципа Банаха сжатых отображений следует справед-
ливость следующей теоремы. Теорема 6.4.Пусть конус K нормален и пусть для некоторых u > θ эле-
0 менты u и F(u ) принадлежат одной составляющей конуса K . Тогда для
0
0 всех λ, ( λ > 0 ) оператор F(x) имеет на составляющей C (u ) собственный k
0 вектор * x (λ) , отвечающий собственному значению λ . Этот вектор может быть построен методом последовательных приближений
55
1 x
(λ) = F x λ m+1
( ( ) m
)
λ при любом начальном приближении x ∈ C (u ) .
0 k
0 При этом справедлива оценка близости m
µ
(
)
14
.
6 d (x*(λ),x
(λ )) ≤ d (x (λ),x (λ)) . m+1
− µ
1
0
1 Замечание.Неравенство (
)
14
.
6 позволяет также получить оценку отно- сительной погрешности для приближений x (λ), т.е. оценку величины m+1
|| * x (λ) − x
(λ)|| m+1 ,
|| * x (λ)|| и позволяет утверждать, что в методе последовательных приближений наряду с абсолютной погрешностью, так же и относительная погрешность приближенного решения стремится к нулю.
Последнее крайне важно, так как в линейных задачах на собственные
векторы определяющим в оценке точности полученного приближения явля-
ется именно оценка относительной погрешности полученного приближения.
56 ГЛАВА 3. НОВЫЕ АЛГОРИТМЫ И МЕТОДЫ ПОСТРОЕНИЯ ПРИБЛИЖЕНИЙ, СХОДЯЩИХСЯ К ТОЧНОМУ РЕШЕНИЮ ОПЕРАТОРНОГО УРАВНЕНИЯ ВИДА x = Ax + f §7.Об одном итерационном методе решения системы линейных алгебраических уравнений вида x = Ax + f с квадратной матрицей A , в случае, когда спектральный радиус матрицы A , больше чем единица
В работе [69] был предложен метод решения уравнения вида x = Ax + f
(
)
1
.
7
с матрицей A , спектральный радиус которой больше единицы. Этот метод
основан на переходе от уравнения вида ( )
1
.
7
к уравнению y = By + g
(
)
2
.
7
с матрицей B , спектральный радиус которой меньше, чем спектральный
радиус матрицы A (r(B) < r( ) A ). Данный метод был реализован [69] для
неотрицательных матриц A , спектральный радиус которых больше единицы.
Однако этот метод обладает существенно большими потенциальными
возможностями, в силу которых мы предлагаем прием решения уравнений
вида ( )
1
.
7
с матрицами A , необязательно являющихся неотрицательными
матрицами. Данный прием основан на предварительном преобразовании
уравнения ( )
1
.
7
к новому уравнению вида ( )
2
.
7
, для которого, в случае
выполнения определенных условий, будет выполнено неравенство: r(B) < 1
и, следовательно, для решения которого может быть использован метод
последовательных приближений: x
= Bx + f , (m =
,...)
1
,
0
m+1 m
при любом начальном приближении x .
0
Переходим к описанию этого метода.
Занумеруем собственные значения λ матрицы A в порядке убывания их
абсолютных величин, т.е. ρ(A)=λ1≥|λ2|≥...≥|λn|. Тогда всякая точка λ спектра
57
σ(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 , входящей в уравнение ( )
1
.
7
. Ниже
предполагается, что A - вполне непрерывный оператор. Соответствующий метод основан на результатах работ В.Я Стеценко, Т.А. Костенко, В.А. Семилетова и заключается в следующем.
Пусть у оператора A среди собственных значений только одно больше
единицы, тогда:
10) нормируем собственные векторы * x и * l матрицы A и
* A ,
соответственно условием
* l ( * x ) = ;
1
20) по матрице A строим матрицу B согласно формуле def
*
* Bx = Ax − λ l (x)x ,
1
где λ = r( ) A . При этом явный вид матрицы B может быть найден по виду
1
матрицы A и виду векторов * x и * l . Спектр матрицы B расположен внутри
круга с центром в начале координат и радиусом равным единице, что
позволяет применять для решения уравнения с матрицей B метод
последовательных приближений.
Как установлено в [69] наибольшее собственное значение матрицы B
будет совпадать со вторым собственным значением λ матрицы A , при этом
2
λ < λ и, следовательно, спектральный радиус матрицы B будет меньше
2
1
спектрального радиуса матрицы A . Если при этом λ < 1, то матрица B
2
58
является оператором сжатия. В этом случае соответствующее уравнение ( )
2
.
7
имеет и притом единственное решение и это решение можно получить по
методу последовательных приближений y
= By + g (m =
,...)
1
,
0
m+1 m
при этом мы можем найти это решение с любой наперед заданной точностью.
Указанная схема позволяет решать уравнения с оператором A (ρ(A)>1, |λ2|<1), если удастся установить связь между решениями xA и xB уравнений
(
)
1
.
7
и ( )
2
.
7
соответственно. Для установления соответствующей связи
предположим, что xA является решением уравнения ( )
1
.
7
, тогда, очевидно, в
силу ( )
3
.
7
имеем xA-BxA=f+λ1l*(xA)x*
и в случае, если ρ(B)<1, отсюда получаем xA=(I-B)-1[f+λ1l*(xA)x*],
т.е.
−1
∗
−1
∗ x = ( I − B ) f + λ l ( x )⋅( I − B ) x = A 1 A
4
1
4
2 3
−1 ∗
= x
+ , B
⋅ c ( I −B ) x
так как, очевидно, что xB=(I-B)-1f – это решение уравнения x=Bx+f. Тем самым установлено, что xA=xB+c(I-B)-1x*. Введем обозначение (I-B)-1x*=yB.
Ясно, что yB – решение уравнения y=By+x* и так как Bx*=θ, то yB=x*. Таким
образом, установлено, что x A=xB+cx*.
(
)
4
.
7
Итак, решение уравнения ( )
1
.
7
можно представить в виде суммы
решения xB уравнения ( )
2
.
7
при g=f и собственного вектора x*. В случае если
собственный вектор x* точно не известен, а известно некоторое приближение
∗ x~ к x*, то решение уравнения (
)
1
.
7
можно представить в виде суммы
решения xB уравнения ( )
2
.
7
при g=f и решения yB уравнения ( )
2
.
7
при g= ∗ x~ .
Это значит, что вместо того, чтобы решать уравнение с оператором A
(напомним, что в общем случае ρ(A) может быть больше 1), достаточно
решить 2 раза уравнение ( )
2
.
7
: один раз с правой частью f, второй раз с
59
правой частью x*.
Остается в этой схеме объяснить, как находить множитель c в формуле
(
)
4
.
7
. Для этого достаточно подставить выражение ( )
4
.
7
в уравнение ( )
1
.
7
, в
результате чего мы получим уравнение с одной скалярной неизвестной c, что
позволяет легко найти c. После этого c подставляем в ( )
4
.
7
и в результате мы
находим решение уравнения ( )
1
.
7
.
В реальной ситуации нам не всегда бывают известны векторы x* и l*,
однако, существуют методы, позволяющие найти приближения к этим
элементам. Предположим, что ∗ ~ x~ и ∗ l достаточно близкие приближения к x*
и l* соответственно. Тогда оператор
~
~∗
~∗ Bx = Ax − λ l (x)x
1
достаточно близок к оператору B и поэтому ~
ρ( B ) ≈ ρ( B ) , при этом не
исключено, что ~
ρ( B ) < 1. В результате мы получили возможность
использовать изложенную схему отыскания приближенного решения x~ B
уравнения с оператором ~B , которое в силу сказанного будет достаточно
близко к решению xB. Тем самым мы имеем возможность приближенного решения уравнения с оператором A в тех случаях, когда x* и l* точно
неизвестны. Пример1. Рассмотрим систему линейных алгебраических уравнений вида
(
)
1
.
7
, где
6
.
0
7
.
0
2 A =
, f = .
7
.
0
6
.
0
1
− 54545
.
4
*
Точное решение x =
.
− 45454
.
5
Для отыскания собственных векторов
* x и
* l матриц A и
* A ,
соответствующего собственного значения λ = r( ) A воспользуемся способом,
1
изложенном в §6.
В данном случае
*
* T
70711
.
0 r( ) A = 3
.
1 x = (l ) =
.
70711
.
0
60
Заметим, что r( ) A = 3
.
1 > 1 поэтому решение уравнения (
)
1
.
7
методом
последовательных приближений не представляется возможным. В результате
применения формулы ( )
3
.
7
матрица B примет следующий вид:
− 05
.
0
05
.
0
B =
, из которого следует, что r(B) = 1
.
0 < 1 .
05
.
0
− 05
.
0
С помощью метода последовательных приближений решаем уравнение x = Bx + f . Этот метод сходится достаточно быстро, так как r(B) = 1
.
0 . В
качестве начального приближения x выберем x = f .
0
0
Итерации метода
последовательных приближений представим в виде таблицы. Таблица 18 m
Приближения x m
1 (1.95000,
1.05000)
2 (1.95500,
1.04500)
3 (1.95450,
1.04550)
4 (1.95455,
1.04545)
5 (1.95454,
1.04545)
10 (1.95454,
1.04545)
Подставим
* x ≈ x + c ⋅ x A
10
в ( )
1
.
7
, получаем
− 21213
.
0
195000
.
c ⋅
=
,
− 21213
.
0
195000
.
откуда c = 9
− .19239 . Поэтому решение x исходного уравнения: A
− 5454
.
4
x =
. A
− 4545
.
5
Как показывает практика, существуют примеры, в которых после
однократного применения формулы ( )
3
.
7
у полученной матрицы B
спектральный радиус снова остается большим единицы. В случаях, когда
среди собственных значений матрицы A есть значение меньше единицы,
61
тогда к полученной матрице B следует повторно применить формулу ( )
3
.
7
,
считая, что A = B , * x - собственный вектор полученной ранее матрицы B , * l -
собственный вектор матрицы * B ( * B -матрица сопряженная B ), а r(B) -
спектральный радиус матрицы B .
Приведем пример соответствующий этому случаю. Пример 2. Рассмотрим систему ( )
1
.
7
, где
1 3 4
1
A = 2 3 1 , f = 1 .
2 2 1
1
− 0.1667
Точное решение * x = − 0.3333 .
0
Применяя способ, изложенный в §6 отыскания собственных векторов * x
и *l матриц A и * A , а также собственного значения λ = r( ) A матрицы A
1
(при этом в качестве начального приближения взяты векторы
= (
)T l
1
,
1
,
1
и
0
= (
)T y
1
,
1
,
1
) находим, что в данном случае
0
0.6794
0.4668
r( ) A = 25
.
6
, * x = 0.5617 , *l = 0.7331 .
0.4720
0.4944
Применяя преобразование ( )
3
.
7
к матрице A , получаем матрицу B :
1
− 0.9854 − 0.1180
1.8971
B =
1
0.3585
0.4221
− 0.7387
0.6207
− 0.1661 − 0.4609
у которой r(B) = 9
.
1 > 1 .
Повторно применяя к матрице B преобразование ( )
3
.
7
(при этом для
1
отыскания собственных векторов * x и * l матриц B и * B , ( * B - матрица
1
1
1
сопряженная B ) и спектрального радиуса матрицы B в качестве начального
1
1
приближения взяты векторы = (
)T l
1
,
1
,
2
и
= ( ,
1
,
1
), получаем матрицу B :
0
)T y
2
0
2
62
− 0.0394 − 0.1641 0.5903
B =
,
2
0.0627
0.4365
0.3302
0.1661
− 0.1439 0.1672
у которой r(B) = 6
.
0 < .
1
С помощью метода последовательных приближений решаем уравнение x = B x + f . После 45 итераций получаем следующее приближение к решению
2
уравнения x = B x + f :
2
1.5125
x =
.
45
1.1825
1.2980
Далее, подставив x ≈ x + c ⋅ x* , B
45 B B
1
1
1
в уравнение x = B x + f находим c , а затем соответственно x - решение
1
1 B
1 B
уравнения вида x = B x + f . Аналогично, подставив
1
* x ≈ x + c ⋅ x A
1 B A A
в уравнение ( )
1
.
7
, найдем
− 0.1667
x =
. A
− 0.3333
0.0000
В действительности существуют и такие примеры, в которых даже после
двукратного использования преобразования ( )
3
.
7
получаем некоторую
матрицу, спектральный радиус которой все еще больше единицы. Продолжая
применять преобразование ( )
3
.
7
к только что полученной матрице мы можем
рассчитывать получить такую матрицу, спектральный радиус которой
меньше единицы (это возможно только в случаях, если среди собственных
значений исходной матрицы исходной матрицы A есть значение меньше
единицы), что позволяет применить к ней метод последовательных
приближений для отыскания решения уравнения вида x = B x + f , где s - s
общее количество полученных матриц B . Связь между решениями
63
уравнений вида x = B x + f и x = B x + f можно установить следующей s −1 s
формулой: x
= x ( B ) + c
⋅ x *
(
B n s B B
,
)
6
.
7 s − 1 s − 1 s − 1
где B - последняя полученная матрица, для которой r(B ) < 1, s s n - число итераций для уравнения вида x = B x + f , s cB - скалярный множитель, s −1 x *B - собственный вектор матрицы B , отвечающий r(B ) , s − 1 s 1
− s 1
− x (B ) - вектор решения уравнения вида x = B x + f , n s s xB - вектор решения уравнения вида x = B x + f . s−1 s −1
При этом A = B .
0 Пример 3. Рассмотрим систему вида ( )
1
.
7
, где
1 1 2 3
1
2 1 3 1
1 A =
, f =
.
4 2 3 2
1
3 1 1 1
1
Применяя способ, изложенный в §6, отыскания собственных векторов * x
и *l матриц A и * A , а также спектрального радиуса матрицы A (при этом в
качестве начального приближения взяты векторы T l = (
)
1
,
1
,
1
,
2
и T y = ,
1
(
)
1
,
1
,
2
),
0
0
находим:
4229
.
0
6156
.
0
3168
.
0
*
4741
.
0
*
r( ) A =
,
87
.
7 x =
, l =
.
6866
.
0
5446
.
0
3534
.
0
4732
.
0
Используя преобразование ( )
3
.
7
к матрице A , получаем матрицу B :
1
− 0503
.
1
− 0553
.
0
1859
.
0
4239
.
1
− 2983
.
0
− 1829
.
0
9666
.
0
7666
.
0
B =
,
1
6715
.
0
2869
.
0
0551
.
0
− 5585
.
0
2867
.
1
1182
.
0
− 5158
.
0
− 3170
.
0
у которой r(B) = 3
.
2 > 1 .
64
Повторно применяя к матрице B преобразование ( )
3
.
7
(при этом для
1
отыскания собственных векторов * x и * l матриц B и * B , ( * B - матрица
1
1
1
сопряженная B ) и спектрального радиуса матрицы B в качестве начального
1
1
приближения взяты векторы T l = ,
1
(
)
1
,
1
,
2
и T y =
,
1
,
1
(
)
1
,
2
), получаем матрицу B :
0
0
2
− 3265
.
2
− 1969
.
0
5630
.
0
4086
.
2
− 3980
.
0
− 1940
.
0
9960
.
0
− 6897
.
0
B =
,
2
2944
.
1
3560
.
0
− 1290
.
0
− 0391
.
1
2968
.
2
2302
.
0
− 8143
.
0
− 0963
.
1
у которой r(B ) все еще больше единицы.
2
В случаях многократного использования формулы ( )
3
.
7
при реализации
предложенного метода, можно установить общую связь между матрицами B и B , считая что A = B : s 1
− s
0 B x = B x − r ( B
) ⋅ l *
*
( 7
.
7 )
*
( x ) ⋅ x s s − 1 s − 1 B B s s
−
−
1
1
Повторно применяя к матрице B теперь уже преобразование ( 7
.
7 ) (при
2
этом для отыскания собственных векторов * x и * l матриц B и * B , ( * B -
2
2
2
матрица сопряженная B ) и спектрального радиуса матрицы B в качестве
2
2
начального приближения взяты векторы = (
,
1
,
1
,
1
и
=
), получаем
0
(
)T y
1
,
1
,
1
,
2
0
)T l
2
матрицу B :
3
2148
.
0
0847
.
0
− 1892
.
0
4509
.
0
− 1994
.
0
− 1720
.
0
9373
.
0
− 8426
.
0
B =
,
3
0540
.
0
2186
.
0
2382
.
0
− 0836
.
0
2854
.
0
0074
.
0
− 2189
.
0
4532
.
0
у которой r(B ) = 81
.
0
< 1.
3
С помощью метода последовательных приближений решаем уравнение x = B x + f .
3
После 30 итераций получаем следующее приближение к решению
уравнения x = B x + f :
3
65
5381
.
2
x B
.
30 ( 3 )
− 7879
.
0
=
9645
.
0
7556
.
2
Далее используя формулу ( )
6
.
7
, получаем решение исходного
уравнения ( )
1
.
7
:
9983
.
0
− 4958
.
2
x =
. A
− 4983
.
1
4974
.
1
Возможности применения этого метода достаточно значительны, о чем в
частности свидетельствуют рассмотренные выше примеры. §8. Получение двусторонних оценок точного решения
* x операторного уравнения вида x = Ax + f , в случае, когда спектральный радиус не обязательно меньше единицы.
В данном параграфе предлагается метод получения оценок вида u ≤ x* ≤ v ,
)
1
.
8
(
где * x - решение линейного операторного уравнения второго рода x = Ax + f ,
)
2
.
8
(
где A - линейный оператор, действующий в пространстве E , f - заданный
элемент пространства E .
Пространство E предполагается полуупорядоченным при помощи конуса K , неотрицательных элементов.
При этом в параграфе используются понятия и терминология банаховых
пространств, полуупорядоченных с помощью конуса Крейна K (K ⊆ E).
Наличие оценок вида
)
1
.
8
(
, которые естественно назвать двусторонними
оценками решения, представляется достаточно важным и информативным. В
самом деле оценка вида
)
1
.
8
(
позволяет утверждать, что нам известны
приближения u к решению * x уравнения
)
2
.
8
(
«по недостатку», а также n
66
приближения v к * x «по избытку», при этом элементы x* − u , и
* v − x - n n n
представляются как оценки (векторные) для решения * x . Если конус K
обладает свойством нормальности, то величина погрешности, с которой мы
знаем эти приближения к решению * x , характеризуется нормой разности δ ,
которое не превосходит величины v − u :
δ ≤ v − u .
Отсюда следует важность получения оценок u,v решения * x .
Отметим, что для отыскания приближений u ,v , известны разные методы n n
[36]. В данном параграфе предлагаются новые подходы к получению таких
оценок u,v неизвестного решения * x уравнения
)
2
.
8
(
. Соответствующие
оценки базируются на следующих теоремах [66]: Теорема 8.1.Пусть x
, x , x
(n = ,1
,
0
)
,...
2 соответствующие n− p n n+ p приближения к решению * x метода последовательных приближений x
= Ax + f .(m =
,
1
,
0
)
,...
2 .
)
3
.
8
( m 1
+ m Подчеркнем, что при этом сходимость этих последовательных приближений к * x заранее не предполагается. Пусть постоянная γ такова, что γ ∈ [ )
1
;
0 и при этом выполнено неравенство x
− x ≤ γ x − x
)
4
.
8
( n+ p n
( n n− ).p Тогда для решения * x уравнения
)
2
.
8
( (если это решение существует) справедлива следующая оценка
γ x* ≤ x
+
(x
− x ) , n+ p n+ p n
1 − γ которую естественно назвать априорной оценкой “сверху” неизвестного решения * x . Теорема 8.2.Пусть x
, x , x
(n = ,1
,
0
)
,...
2 соответствующие n− p n n+ p приближения к решению * x метода последовательных приближений
)
3
.
8
( . Пусть постоянная β такова, что β < 1 и при этом выполняется неравенство
67
β (x − x
≤ x
− x ,
)
5
.
8
( n n− p ) n+ p n тогда справедлива следующая априорная оценка “снизу” для неизвестного решения * x :
β x* ≥ x
+
(x
− x ) . n+ p n+ p n
1 − β
Важно подчеркнуть, что приведенные оценки “снизу” и “сверху”
являются на самом деле достаточно точными даже в тех случаях, когда
приближения x , x , x (n = ,1
,
0
)
,...
2
достаточно далеки от точного решения n− p n n+ p
* x . Удивительным является и тот факт, что оценки “снизу” и “сверху” для * x
могут сходиться к решению даже в том случае, когда метод
последовательных приближений
)
3
.
8
(
вообще не сходится (последнее
заведомо будет иметь место в случае когда спектральный радиус оператора A больше чем единица). Предложенные ниже примеры иллюстрируют такую
ситуацию.
Приведем примеры применения вышеизложенного метода получения
двусторонних оценок. Пример 1. Рассмотрим уравнение вида
)
2
.
8
(
, где
1
.
0
15
.
0
13
.
0
14
.
0
1
.
0
1
12
.
0
14
.
0
13
.
0
11
.
0
14
.
0
2
A =
15
.
0
11
.
0
12
.
0
1
.
0
12
.
0
, f = 3 .
1
.
0
1
.
0
13
.
0
13
.
0
12
.
0
4
14
.
0
13
.
0
17
.
0
1
.
0
12
.
0
5
85367655
.
5
04617563
.
7
Точное решение данного уравнения
*
x = 64556639
.
7
, а спектральный
61739842
.
8
11023145
.
10
радиус r( ) A = 6199
.
0
.
Тогда точное решение
* x исходного уравнения заключено между
следующими границами:
−2 85772
.
−2 84934
.
−
3.
93645
−
*
392608
.
≤ x ≤
.
−
4 94699
.
−
4 93433
.
−2.
62346
−2.
61559
Важно также подчеркнуть, что приближения x , x , x (n = ,1
,
0
)
,...
2
могут n− p n n+ p
быть получены не только по методу последовательных приближений, но и по
методу однопараметрического итеративного агрегирования [72]. В данном
случае получим два вектора, находящиеся в определенной степени близости
от точного решения * x , причем точность полученных таким способом
векторов будет выше, чем точность соответствующих приближений,
полученных по методу однопараметрического итеративного агрегирования.
Отметим также, что хотя при помощи этих векторов нельзя будет оценить
точное решение * x «снизу» и «сверху», тем не менее, их степень точности
будет намного выше, чем у соответствующих оценок точного решения * x .
Приведем соответствующий пример. Пример 4. Рассмотрим уравнение вида
)
2
.
8
(
, где
Тогда точное решение * x исходного уравнения можно оценить при
− 85419
.
2
− 85438
.
2
− 93189
.
3
− 93169
.
3
помощи векторов
и
, при этом не обязательно точное
− 94150
.
4
− 94150
.
4
− 62011
.
2
− 62029
.
2
решение * x заключено между этими векторами.
Как видно из этого примера, по сравнению с предыдущим, заметно
повысилась точность оценки решения. В данном случае точность составляет
10-3. Пример 5. Рассмотрим уравнение вида
)
2
.
8
(
, где
73
По предложенному в этом параграфе методу автором составлена
программа на языке программирования TURBO PASCAL. §9. О некоторых подходах к уточнению границ решения операторных уравнений вида x = Ax + f в случае, когда спектральный радиус r( ) A не обязательно меньше единицы.
В данном параграфе предлагается способ уточнения оценок вида
)
1
.
8
(
.
Приведенные оценки могут быть уточнены, если известно, что оператор p A обладает дополнительными свойствами, например, если этот оператор u -ограничен снизу [66].
0
Оператор p A
называется u -ограниченным
снизу, где u > θ
0
0
фиксированный элемент, если для каждого x > θ существует такое
δ = δ (x) > 0 , что выполняется неравенство Apx ≥ δ (x)u .
0
В частности Apu ≥ δ u (δ > 0 .
)
1
.
9
(
0
)
0
0 0
Возможность улучшения полученных оценок для u - ограниченных
0
снизу операторов основана на том, что для таких операторов из неравенства x
− x ≤ γ x − x
,
)
2
.
9
(
n+ p n
( n n−p)
где x , x , x - приближения к точному решению * x , полученные по методу n+ p n n− p
последовательных приближений ( n и p - фиксированные натуральные числа
(n ≥ p)), причем 0 < γ < 1, вытекает более сильное, чем неравенство x
− x s−
≤
1
γ (x
− x ) , n+ sp n+ (s−1) p n+ p n
(последнее справедливо для любого натурального s ≥ 2 , благодаря
положительности, а потому и монотонности линейного оператора A),
неравенство вида x
− x s−
≤
1
γ x
− x
(s
−
)
(
) σ
, n+ sp n+ (s−1) p n+ p n n, p
74
где σ (s) ≥ θ . n, p
Справедлива следующая теорема [66]. Теорема 9.1.Пусть оператор p A является u - ограниченным снизу.
0 Пусть выполнено неравенство
)
2
.
9
( и γ > δ .
0 Тогда имеет место следующее уточнение оценки “сверху” для решения
* x уравнения
)
2
.
8
( :
γ
δ x* ≤ x
+
(x
− x ) − u , n+ p n+ p n
1 − γ
(1− γ )(1 − δ ) 0
0 где γ и δ определяются согласно
)
2
.
9
( и
)
1
.
9
( , а
0
δ = δ [γ (x − x x x n n− p ) − (
− n+ p n )] >
.
0 Теорема 9.2.Пусть оператор p A является u - ограниченным снизу.
0 Пусть для последовательных приближений x , x , x , где n и p n+ p n n− p фиксированные натуральные числа (n ≥ p), выполняется неравенство
β (x − x
≤ x
− x ,
)
3
.
9
( n n− p ) n+ p n причем 0 < β < 1 и β > δ .
0 Тогда имеет место следующее уточнение оценки “снизу” для решения * x уравнения
)
2
.
8
( :
β
δ x* ≥ x
+
(x
− x ) +
1 u , n+ p n+ p n
1 − β
(1 − β )(1 − δ ) 0
0 где β и δ определяются в соответствии с неравенствами
)
3
.
9
( и
)
1
.
9
( , а
0
δ = δ x
− x − β x − x
>
1
([ n+p n) ( n n−p)] .0
1
Ниже будут рассмотрены примеры, в которых реализовывается метод
получения оценок точного решения * x операторного уравнения вида
)
2
.
8
(
и
способ улучшения этих оценок. Также рассматривается вариант
предложенного метода в “связке” с методом однопараметрического
итеративного агрегирования. К полученным таким методом оценкам точного
решения
* x операторного уравнения вида
)
2
.
8
(
применяется способ
улучшения этих оценок.
75 Пример 1. Рассмотрим уравнение вида
)
2
.
8
(
, где
0 0
. 5
01
. 2
01
.
0 3
.
1
1
0 0
. 6
0 2
. 7
0 2
. 9 01
. 3
2 A =
, f =
.
0 4
. 1 0 053
.
01
. 1 0 21
.
3
01
. 7
0 04
.
0 3
. 6 0.
22
4
В данном примере спектральный радиус r( ) A = 727
.
0
. В качестве
1
1
начального приближения выберем вектор x = . Точное решение
0
1
1
.
71
35319126
.
9 39508034 x* =
. Зафиксируем n = ,
5 p = 2 , получим:
.
9 99663311
.
11 77896844
4 338243
.
5650142
.
6 350149
.
5822515
.
7 505754
.
8 396079
. x =
, x =
, x =
.
3
6583639
.
5
8189273
.
7
9 041989
.
8110907
.
9 849658
.
10 759054
.
Здесь γ = 53358
.
0 , β = 52302
.
0
. Тогда вектор решения * x данного уравнения
заключен между следующими векторами:
711771
.
715096
.
9 37233
.
9 41461
.
*
≤ x ≤
.
9 97700
.
10 01750
.
1175622
.
1179941
.
Как видно точность полученных оценок составляет 10-1. Теперь применим
к полученным результатам способ улучшения оценок, который был описан
1
1
выше. Выберем в качестве u = . Тогда оценки точного решения * x примут
0
1
1
следующий вид:
76
713307
.
713826
.
9 38769
.
9 40192
.
*
≤ x ≤
.
9 99236
.
10 00481
.
1177158
.
1178671
.
Точность у полученных оценок возросла и составляет 10-2.
Воспользуемся теперь для этого же примера синтезом метода получения
оценок точного решения * x операторного уравнения вида
)
2
.
8
(
и метода
однопараметрического итеративного агрегирования. В данном случае
приближения x , x , x получены по методу однопараметрического n+ p n n− p
итеративного агрегирования.
Здесь также n = ,
5 p = 2 . Получим соответствующие приближения:
713136
.
713723
.
713526
.
3 34939
.
9 3
. 9738
9 39514
. x =
, x =
, x =
.
3
9 97545
.
5
9 9.9566
7
9 99668
.
1170409
.
1178115
.
1177909
.
Здесь γ =
,
05071
.
0
β = − 33579
.
0 .
Тогда точное решение * x можно оценить при помощи следующих
векторов:
713576
.
713516
.
9 39570
.
9 39502
.
и
.
9 99642
.
9 99674
.
1177961
.
1177898
.
Как видно по сравнению с предыдущими оценками здесь заметно
возросла точность и теперь она составляет 10-3. В данном случае
модификация предложенного метода намного улучшает оценки точного
решения * x операторного уравнения вида
)
2
.
8
(
.
Рассмотрим теперь пример с таким линейным оператором A , у которого
спектральный радиус r( ) A > 1. Пример 2. Рассмотрим уравнение вида
)
2
.
8
(
, где
77
0 4
. 5 01
. 2
01
.
0 3
.
1
1
0 0
. 6 0 2
. 7 0 2
. 9 01
. 3
2 A =
, f =
.
0 4
. 1 053
.
01
. 1 0 21
.
3
01
. 7 0 47
.
0 3
. 6 0.
22
4
В данном примере спектральный радиус r( ) A = 015
.
1
. В качестве
1
1
начального приближения выберем вектор x = . Точное решение
0
1
1
−
9741086
.
158
*
−
8110005
.
114
x =
. Зафиксируем n=8, p=2, тогда получим:
−
2641594
.
181
−
3613668
.
182
14 52504
.
19 91487
.
2547222
.
12 31833
.
16 26772
.
20 33980
. x =
, x =
, x =
.
6
18 73744
.
8
24 95073
.
10
3135698
.
20 35843
.
26 65614
.
3314946
.
Отметим тот факт, что в данном случае приближения, полученные по
методу последовательных приближений не сходятся к решению уравнения
вида
)
2
.
8
(
, т.к. r( ) A > 1. Тем не мене получим следующие оценки точного
решения * x , где γ =
,
03108
.
1
β = 03106
.
1
:
−159.
02434
−15889897
.
−
114 84789
.
−
*
114.
75602
≤ x ≤
.
−
181 32226
.
−
18117774
.
−182.
42023
−182.
27374
Итак, несмотря на то, что метод последовательных приближений в
данном случае фактически “расходится”, полученные оценки достаточно
близки от точного решения * x .
Воспользуемся теперь модификацией метода получения оценок точного
решения
* x
операторного
уравнения
вида
)
2
.
8
(
и
метода
78
однопараметрического итеративного агрегирования. Здесь также n=8, p=2,
1
1 x = . Получим соответствующие приближения:
0
1
1
159
−
01063
.
−158 97515
.
−158 97413
.
−114 84337
.
−114 81199
.
−114 81103
. x =
, x =
, x =
.
6
−18130776
.
8
−18126545
.
10
−18126419
.
−182 41119
.
−182 36289
.
−182 36141
.
Здесь γ =
,
03086
.
0
β = 02873
.
0 . Тогда точное решение * x можно оценить при
помощи следующих векторов:
−158.
974106
−158.
974214
−
114.
811001
−
114.
811110
и
.
−
181 264158
.
−
181 264266
.
−182.
361368
−182.
361475
В данном случае заметно возросла точность и теперь она составляет 10-3.
Применение в данном случае модификации предложенного метода намного
улучшает оценки точного решения * x операторного уравнения вида
)
2
.
8
(
. Но
применение здесь способа улучшения оценок не увеличивает точность
полученных оценок. Напомним еще раз, что в данном случае r( ) A > 1.
Итак, применять способ улучшения полученных оценок точного решения
* x , возможно только в том случае, если спектральный радиус оператора A
меньше единицы r( ) A < 1.
Если до этого мы рассматривали примеры, у которых линейный оператор A - матрица, у которой все элементы были положительными, то теперь
рассмотрим такие примеры, у которых матрица A , таким свойством не
обладает. Пример 3. Пусть дано уравнение вида
)
2
.
8
(
, где
0 0
. 5
−01
. 2
0 4
. 7
−0 3
.
1
1
−0 0
. 6
0 2
. 7
0 2
. 9
01
. 3
2 A =
, f =
.
0 4
. 1
0 053
.
01
. 1
−
0 21
.
3
−01
. 7
0 04
.
−0 3
. 6
0 22
.
4
79
В данном примере спектральный радиус r( ) A = 7604
.
0
. В качестве
1
1
начального приближения выберем вектор x = . Точное решение
0
1
1
7990584
.
0
*
5837095
.
4
x =
. Зафиксировав n=8, p=2, тогда получим:
1281162
.
3
7453674
.
3
88105
.
0
84543
.
0
825725
.
0
59444
.
4
59210
.
4
588753
.
4
x =
, x =
, x =
.
6
20047
.
3
8
17126
.
3
10
153246
.
3
67094
.
3
70245
.
3
720579
.
3
Здесь γ =
,
43655
.
1
β = 55320
.
0
. Тогда координаты вектора точного решения
* x можно оценить при помощи следующих векторов:
80133
.
0
89057
.
0
58460
.
4
59979
.
4
и
.
13094
.
3
21254
.
3
74302
.
3
66093
.
3
Как видно в этом случае точное решение * x нельзя оценить “снизу” и
“сверху”, при помощи полученных векторов, как, например, это было в
случае, когда линейный оператор A - матрица с положительными
элементами.
Попробуем применить способ улучшения оценок в данном случае.
1
1
Выберем в качестве u = . Тогда для оценки точного решения * x получим
0
1
1
следующие векторы:
80018
.
0
85749
.
0
58345
.
4
56671
.
4
и
.
12979
.
3
17946
.
3
74187
.
3
62786
.
3
Принципиально ситуация не изменилась.
80
А теперь применим к рассматриваемому примеру модификацию методов
получения оценки точного решения * x и однопараметрического итеративного
1
1
агрегирования. Здесь также x = , n=8, p=2. Получим следующие
0
1
1
приближения:
00624
.
1
91708
.
0
86711
.
0
60087
.
4
59250
.
4
58861
.
4
x =
, x =
, x =
.
6
31259
.
3
8
23603
.
3
10
19080
.
3
55834
.
3
63808
.
3
68338
.
3
Здесь γ =
,
59085
.
0
β = 46347
.
0
. Тогда точное решение можно оценить при
помощи следующих векторов:
82395
.
0
79495
.
0
58526
.
4
58301
.
4
и
.
15172
.
3
12547
.
3
72251
.
3
74880
.
3
Итак, в случае, когда матрица A ( r( ) A < 1) не является положительной, нельзя
получить оценки снизу” и “сверху” точного решения * x и, соответственно
получить уточнение полученных оценок.
Если в предыдущем примере r( ) A < 1, то теперь рассмотрим пример в
котором r( ) A > 1. Пример 4. Пусть дано уравнение вида
)
2
.
8
(
, где
0 0
. 5
−01
. 2
0 4
. 7
−0 3
.
1
1
−0 6
.
0 2
. 7
0 5
. 9
01
. 3
2 A =
, f =
.
0 6
. 9
0 53
.
0 7
. 1
−
0 21
.
3
−0 2
. 7
0 0
. 4
−0 3
. 6
0 2
. 2
4
81
В данном примере спектральный радиус r( ) A = 26617
.
1
. В качестве
1
1
начального приближения выберем вектор x = . Точное решение
0
1
1
− .
7
523184
.
4 206156 x* =
. Зафиксировав n=16, p=1, получим:
− .
8 446543
.
11846489
15575808
.
199 21668
.
254 24363
.
87 24385
.
109 35176
.
137 34191
. x =
, x =
, x =
.
15
332 23149
.
16
422 91068
.
17
537 72694
.
−144 35238
.
−18592579
.
−23856595
.
Как видно, приближения, полученные по методу последовательных
приближений, “удаляются” от точного решения * x . Тем не менее, точное
решение * x можно оценить при помощи следующих векторов:
−7.
59769
−7.
49774
415304
.
4 20389
.
и
.
−
8 61703
.
−
8 40846
.
1191803
.
1182240
.
Отметим, что полученные оценки обладают достаточно высокой
точностью.
Применение к полученным векторам способа улучшения оценок не дает
ожидаемого эффекта.
Из проделанных вычислений следует, что использование в данном случае
модификации методов получения оценки точного решения
* x и
однопараметрического итеративного агрегирования не дает выигрыша в
точности.
Рассмотрим теперь пример с таким оператором A , спектральный радиус
которого «намного» больше единицы. Пример 5. Пусть дано уравнение вида
)
2
.
8
(
, где
82
0 9
. 5 −01
. 2
0 9
. 7
−0 3
.
1
1
−0 6
.
0 8
. 9
0 5
. 9
0 9
. 3
2 A =
, f =
.
0 9
. 9
0 38
.
0 7
. 1
−
0 21
.
3
−0 2
.
0 8
. 4
−0 0
. 3 0 9
. 2
4
В данном примере спектральный радиус r( ) A = 0022
.
2
. В качестве
1
1
начального приближения выберем вектор x = . Заметим, что в данном
0
1
1
− .
2
189895
− .
5 620456
примере точное решение x* =
. Зафиксируем n=4, p=1. Для оценки
− .
2 652581
− .
2
545337
точного решения * x ,получим соответствующие приближения:
1051584
.
17 69660
.
27 78023
.
25 31423
.
5016418
.
95 00877
. x =
, x =
, x =
.
3
17 47908
.
4
3055574
.
5
52 02921
.
2325953
.
44 03518
.
8219429
.
Здесь γ =
,
83672
.
1
β = 40426
.
1
.
Тогда точное решение заключено между следующими векторами:
−7 24697
.
564526
.
−
60.
76652
−
*
3.
43134
≤ x ≤
.
−
22 56253
.
4 89195
.
−50.
35785
−1.
57026
Как видно, полученные оценки очень далеки от точного решения * x , тем
не менее, они позволяют получить “нижнюю” и “верхнюю” границы точного
решения * x операторного уравнения вида
)
2
.
8
(
. Использование в данном
случае способа улучшения полученных оценок ситуацию не изменяет.
Ситуация не изменяется и при применении модификации методов получения
оценки точного решения
* x и однопараметрического итеративного
агрегирования.
83
Итак, из рассмотренных выше примеров можно сделать вывод, что
предложенный выше способ и метод в [59] и их модификации обладают
большим потенциалом.
Оценку v решения * x назовем активной оценкой решения уравнения вида
)
2
.
8
(
сверху, если Av + f ≤ v .
Аналогично, оценку u решения * x назовем активной оценкой решения
уравнения вида
)
2
.
8
(
снизу, если Au + f ≤ . u
Очевидно, что наличие активных оценок «сверху» и «снизу» решения * x
позволяет их улучшать. Именно, если u = Au
+ f , v = Av + f n n 1
− n n−1
(n = ,
1 ,...;
2 u = u,v = v) ,
0
0
где u ,v - активные оценки, то u ,v при всех n также являются активными
0
0 n n
оценками. При этом, если r( ) A < 1, то u ,v сходятся к решению * x , причем n n
для всех значений n u ≤ x* ≤ v , n n
то есть мы имеем сходящиеся к решению * x двусторонние приближения.
Понятно, что это свойство активных оценок представляет значительный
интерес, а получение таких оценок представляется весьма актуальным. В
этой связи интересно исследовать полученные выше оценки на предмет
наличия у них свойства активности.
Однако прежде сделаем следующее замечание.
Очевидно, всякое решение * x уравнения
)
2
.
8
(
является для любого
натурального s также решением уравнения x = Asx + f ,
)
4
.
9
(
1
где f = As−1 f + As−2 f + ... + Af + f ,
)
5
.
9
(
1
то есть уравнения
84 x = A x + f
1
1
при s A = A . Оператор s A , очевидно, линеен и положителен одновременно с
1
оператором A . Теорема 9.3. Все оценки, полученные в теоремах 8.1, 8.2, 9.1, 9.2, являются активными.
Доказательство. Ограничимся доказательством активности оценки
«снизу» теоремы 8.2 (для остальных оценок доказательства аналогичны).
Итак, пусть выполнены условия теоремы 8.2.
Пусть в
)
4
.
9
(
и
)
5
.
9
( s = p и p A = A . Тогда, очевидно, для элемента
1
β u = x
+
(x
− x ) достаточно доказать, что
1 n+ p
1 n+ p n
− β A u + f ≥ u .
1 1
1
1
Последнее неравенство эквивалентно неравенству
β
β
(x
− x ) +
(x
− x ) ≥
(x
− x ) , n+ 2 p n+ p
1 n+ 2 p n+ p
− β
1 n+ p n
− β
а это неравенство, в свою очередь, эквивалентность неравенству
1
β
(x
− x ) ≥
(x
− x ) .
1 n+ 2 p n+ p
− β
1 n+ p n
− β
Справедливость последнего неравенства следует из условия теоремы 8.2 и
монотонности оператора A
1
Теорема доказана.
Наличие активных оценок «снизу» и «сверху» решения * x позволяет
использовать более эффективный прием их улучшения, чем итеративные
методы улучшения, изложенный выше. Этот прием приводит к новым
активным оценкам решения. Опишем этот прием на примере его применения
к оценкам в теоремах 8.1, 8.2, полагая, для простоты записи и выкладок, что в
последних p = 1. Теорема 9.4. Пусть числа γ и β удовлетворяют, соответственно, неравенствам
)
4
.
8
( и
)
4
.
8
( , а число m неравенству
1
85
1 [(x − x ) − β(x − x
≥ m
γ x − x
− x − x .
)
6
.
9
( n+1 n n n 1
− ]
1
)
1
[ (
) (
) n n 1
− n+1 n ]
1− β
1− γ Тогда для решения * x уравнения
)
2
.
8
( верна следующая оценка «снизу»:
β
γ
7
.
9
(
)
*
1
x ≥
x +
(x
− x ) + m x x x . n+1 n+1 n
1
+
(
− n+1 n+
)
1 n
1+ m
β
γ
1
1−
1−
Аналогично, если m удовлетворяет неравенству
2
1 [ m
γ (x − x ) − (x − x ) ≥ x
− x − β x − x
)
8
.
9
( n n 1
− n+ n ]
2
1
[(
)
(
) n+1 n n n 1
− ]
1− γ
1− β то
γ
β
)
9
.
9
(
*
1
x ≤
x +
(x
− x ) + m x x x . n+1 n+1 n
2
+
(
− n+1 n+
)
1 n
1+ m
γ
β
2
1−
1−
Остановимся на доказательстве оценки
7
.
9
(
) . Условие
)
6
.
9
( , как нетрудно
проверить, означает справедливость следующего неравенства
(Au + f ) − u ≥ m v − Av + f ,
0
0
1[
(
)
0
0
]
где u и v , соответственно выражаются формулами
0
0
β u = x +
(x − x ) ,
0 n
1 n n 1
−
− β
γ v = x +
(x − x ).
0 n
1 n n 1
−
− γ
Тогда из результатов работы [64] следует справедливость оценки 7
.
9
(
) .
Аналогично, условие
)
8
.
9
( означает, что v − (Av + f ) ≥ m (Au + f ) − u ,
0
0
2 [
0
0 ]
из которого опять на основании [64] вытекает оценка
)
9
.
9
( .
Оценки
7
.
9
(
) и
)
9
.
9
( заведомо лучше оценок в теоремах 8.1, 8.2,
соответственно, если m > 0 и m > 0 . Последнее условие выполняется, если
1
2
конус K телесен, а оператор A переводит ненулевые элементы конуса K во
внутренние элементы K . В случае A = (a ) , n E = R при конусе K векторов с ij
неотрицательными координатами, последнее имеет место, если все элементы
матрицы A положительные.
86 §10. “Гибрид” методов ускорения сходимости монотонных приближений к решению * x уравнения вида x = Ax + f и однопараметрического итеративного агрегирования
В данном параграфе предлагается один вариант метода, позволяющего
строить приближения к решению системы линейных уравнений вида
)
2
.
8
(
,
обладающего достаточно высокой скоростью сходимости. Заметим, что
предлагаемый вариант по существу представляет собой сочетание методов
итеративного агрегирования и использует идею ускорения сходимости для
известного варианта [36] ускорения сходимости метода последовательных
приближений. Предлагаемый в данном параграфе метод по существу
гарантирует достаточно высокую скорость сходимости к исходному
решению и отличается простотой в его реализации. Немаловажной
особенностью этого метода является то, что этот метод способен сходится к
решению уравнения вида
)
2
.
8
(
и в случае, когда спектральный радиус
матрицы A больше единицы r( ) A > 1.
Сущность данного “гибрида” методов для отыскания решения уравнения
вида x = Ax + f ,
)
1
.
10
(
где A – матрица порядка (n × n), f – свободный вектор, n f ∈ R , x –
неизвестный вектор, n x ∈ R , заключается в следующем алгоритме.
Сначала находим такие векторы u ,v , для которых выполняются
0
0
неравенства: u ≤ u = Au + f ,
)
2
.
10
(
0
1
0 v = Av + f ≤ v
)
3
.
10
(
1
0
0
(существование таких векторов будет обеспечено при выполнении условия r( ) A < 1).
Алгоритм поиска векторов u и v был описан в §2.
0
0
Затем из уравнения вида u = Au + f , по u строим u методом
0
1
однопараметрического итеративного агрегирования и из уравнения вида
87 v = Av + f по v строим v методом однопараметрического итеративного
0
1
агрегирования.
Потом определяем поправочные коэффициенты p и q следующим
1
1
образом.
Пусть p ,q - такие два числа, для которых выполняются неравенства:
1
1 u − u ≥ p (v − v ) ,
1
0
1
0
1 v − v ≥ q (u − u ) .
0
1
1
1
0
Здесь p и q определяются из условия
1
1
(u − u )
(v − v ) p
1
0 i
≤
; q
0
1 i
≤
(i = ,1
)
,...
2
.
1
(v − v )
1
(u − u )
0
1 i
1
0 i
В частности можно положить
(u − u )
(v − v ) p
1
0 i
= min
; q
0
1 i
= min
.
1
1 i=1,n (v − v ) i=1,n (u − u )
0
1 i
1
0 i
Тогда решение уравнения вида
)
1
.
10
(
на первой итерации заключено
между элементами u* v*
, , где
1
1
+
+
* v q u
* u p v u
1
1 1
=
, v
1
1 1
=
.
1
1 + p
1
1 + q
1
1
Итак, выше был описан один шаг рекуррентного процесса
предлагаемого метода.
Аналогично, пусть определены u и v , по индукции положим n n
+
+
* v q u
* u p v u n n n
=
, v n n n
=
. n
1 + p n
1 + q n n
Отметим тот факт, что при применении схемы ускорения сходимости
поправочные коэффициенты p и q можно определять другим способом
(отличным от описанного выше). Он заключается в следующем:
−
−
а) возьмем отношения u
( u )
1
0 i (v v )
0
1 i
,
(i = ,1
)
,...
2
(v − v )
0
1 i u
( − u )
1
0 i
88
б) в качестве p выбираем среднее арифметическое, составленное из
1
−
соответствующих координат вектора (u u )
1
0 i , а в качестве q среднее
(v − v )
1
0
1 i
−
арифметическое из соответствующих координат вектора (v v )
0
1 i
,
. u
( − u )
1
0 i
Но как показывают примеры, если определены начальные приближения u
0
и v , удовлетворяющие условиям
)
2
.
10
(
и
)
3
.
10
(
, то возможна такая ситуация,
0
при которой “гибрид” методов ускорения сходимости монотонных
приближений и однопараметрического итеративного агрегирования не
работает, т.к. на некотором шаге при определении * * u ,
будет появляться n vn
недопустимая операция (деление на ноль).
Отметим, что последовательности * u и
* v обладает более высокой n n
скоростью сходимости к точному решению * x , чем метод ускорения
сходимости. Пример 1. Рассмотрим уравнение вида
)
1
.
10
(
, где
2
.
0
3
.
0
1 A =
, f = .
4
.
0
2
.
0
2
692307
.
2
*
Спектральный радиус r( ) A = 546
.
0
. Точное решение x =
. Пусть
846153
.
3
1
− 5
.
2
5
.
2 z =
, тогда u =
, v =
.
0
0
0
1
− 5
.
2
5
.
2
Соответствующие приближения u* и v* , к координатам вектора решения n n
представим в виде таблицы. Таблица 19 Приближения к 1-ой координате вектора решения n
“ u*”
“ v* ” n n
1 2.6667
2.6667
2
Деление на ноль
89 Приближения к 2-ой координате вектора решения
1 4.000
4.000
2
Деление на ноль
В рассмотренном выше примере недопустимая операция возникла из-за
действия параметра, при определении последовательностей u и v методом n n
последовательных приближений.
Но как показывают практика в качестве начальных приближений можно
выбрать такие неотрицательные векторы u и v , которые не будут
0
0
удовлетворять условиям
)
2
.
10
(
и
)
3
.
10
(
, но при этом полученные
последовательности u* и v* будут сходится к точному решению * x , хотя это n n
решение не всегда будет заключено между этими последовательностями. При
этом скорость сходимости в некоторых случаях заметно увеличится. Здесь,
по сути, мы имеем две независимые последовательности u* и v* , сходящиеся n n
к точному решению * x уравнения вида
)
1
.
10
(
.
Рассмотрим соответствующий пример. Пример 2. Рассмотрим уравнение вида
)
1
.
10
(
, где
0.3 0.4 0.1
1
A = 0.1 0.5 0.2 , f = 2 .
0.2 0.3 0.4
3
10.17391304
Точное решение * x = 11.73913043 , а спектральный радиус r( ) A = 828
.
0
.
14.26086956
В качестве начальных приближений возьмем векторы:
1
5
u = 2 ,
0
v = 7 .
0
3
8
Используя вышеизложенный метод, получим приближения u* и v* , n n
между которыми заключено решение исходного уравнения.
Соответствующие приближения u* и v* , к координатам вектора решения n n
представим в виде таблицы.
90 Таблица 19 Приближения к 1-ой координате вектора решения n
“ u*”
“ v* ” n n
1 12.44537815
12.466832216
2 10.65854778
10.43895004
6 10.17369452
10.17378128
9 10.17391466
10.17391530
12 10.17391306
10.17391305
15 10.17391304
10.17391304 Приближения к 2-ой координате вектора решения
1
13.00840336
13.00510274
2 12.94980838
12.16330283
6 11.73867845
11.73872240
9 11.73913495
11.73913590
12 11.73913048
11.73913048
15 11.73913043
11.73913043 Приближения к 3-й координате вектора решения
1 14.54621849
14.52806509
2 15.60339011
14.67062656
6 14.26039228
14.26039700
9 14.26087469
14.26087558
12 14.26086961
14.26086962
15 14.26086956
14.26086956
Как видно из таблицы точность вычислений на 15-м шаге составляет 10-8.
При реализации данного метода значения последовательностей u* и v* n n
можно
находить
для
некоторых
фиксированных
значений
последовательностей u и v , т.е определять значения последовательностей n n u* и v* в “узловых” точках последовательностей u и v , при этом скорость n n n n
91
схождения приближений к решению исходного уравнения заметно
возрастает.
Применим данные рассуждения для вышеизложенного примера, причем
значения * u и * v будут определяться для u , v .
4n
4n
В качестве начальных приближений возьмем следующие векторы:
6
1
u = 5 , v = 2
0
0
4
3
Соответствующие приближения u* и v* , к координатам вектора решения n n
представим в виде таблицы. Таблица 20 Приближения к 1-ой координате вектора решения n
“ u*”
“ v* ” n n
1 11.05524862
11.41860465
2 10.16937891
10.17410479
3 10.17391086
10.17391655
4 10.17391304
10.17391306 Приближения к 2-ой координате вектора решения
1 8.64088398 6.27906977
2 11.73508279 11.73888093
3 11.73912821 11.73913563
4 11.73913042 11.73913046 Приближения к 3-й координате вектора решения
1 9.47513812
6.02325581
2 14.25823541
14.26040731
3 14.26086792
14.26087442
4 14.26086955
14.26086959
Понятно, что если повысить порядок “узловых” точек, то скорость
схождения к вектору решения исходного уравнения увеличится.
92
Можно при помощи следующего графика провести сравнительный анализ
рассмотренных ранее численных методов.
120
100
метод последовательных приближений
и й
80
метод ускорения
ац ер
сходимости
в о
ит
60
гибрид ускорения
ч е ст
сходимости
ли
40
Ко
гибрид ускорения сходимости (узл.)
20
0
1
2
3
4
5
6
7
Порядок точности Рис. 1. Сравнение скорости сходимости «гибрида» методов ускорения
сходимости и однопараметрического итеративного агрегирования с
известными ранее методами.
В данном графике по оси абсцисс указаны количество верных знаков
после запятой, а по оси ординат – количество итераций.
В заключении отметим, что условие монотонной сходимости
приближений к решению * x уравнения вида
)
1
.
10
(
, при решении их гибридом
методов ускорения сходимости и однопараметрического итеративного
агрегирования в рассмотренных примерах не выполняется.
93 §11. Об одном варианте метода ускорения сходимости монотонных приближений к решению уравнения вида x = Ax + f
В этом параграфе приближения “снизу” и “сверху” к точному решению
* x операторного уравнения вида x = Ax + f ,
)
1
.
11
(
где A - матрица порядка (n × n) , f - свободный вектор, n f ∈ R , x -
неизвестный вектор, n x ∈ R , строятся по методу ускорения сходимости
монотонных приближений (см.§2) к точному решению * x уравнения вида
)
1
.
11
(
по следующим формулам[36]:
+
+
)
2
.
11
(
* v q u
* u p v u n n n
=
, v n n n
=
. n
1 + p n
1 + q n n
При построении приближений
)
2
.
11
(
возникают проблемы с выбором
начальных приближений u ,v , для которых выполняются следующие
0
0
неравенства: u ≤ u = Au + f ,
)
3
.
11
(
0
1
0 v = Av + f ≤ v
)
4
.
11
(
1
0
0
(существование таких векторов обеспечивает условие r( ) A < 1). И если в
качестве вектора u всегда можно выбрать свободный вектор f , то с
0
вектором v дела обстоят несколько сложнее (существует определенный
0
алгоритм отыскания векторов u ,v ). Здесь в качестве начальных
0
0
приближений u ,v предлагается выбрать векторы, полученные по
0
0
следующим формулам (см.§7):
β x
+
(x
− x ) , n+ p n+ p n
1 − β
γ x
+
(x
− x ) , n+ p n+ p n
1 − γ
где x , x , x (n = ,1
,
0
)
,...
2
соответствующие приближения к решению * x n− p n n+ p
метода последовательных приближений: x
= Ax + f , n =
n+1 n
(
,
1
,
0
)
,...
2
94
постоянная β такова, что β < [ )
1
,
0 и при этом выполняется неравенство:
β (x − x
≤ x
− x n n− p ) n+ p n
постоянная γ такова, что γ ∈ [ )
1
,
0 и при этом выполнено неравенство: x
− x ≤ γ x − x
n+ p n
( n n− ).p
Заметим, что в данном случае векторы u ,v будут находиться в
0
0
определенной близости от точного решения * x ( u ≤ x* ≤ v ) и при этом для
0
0
них будут выполняться неравенства
)
3
.
11
(
и
)
4
.
11
(
. Отметим, что данный
выбор векторов u ,v увеличивает скорость сходимости двусторонних
0
0
приближений к точному решению * x уравнения
)
1
.
11
(
. Проиллюстрируем
вышесказанное на соответствующем примере. Пример 1. Пусть дано уравнение вида
)
1
.
11
(
, где
0 3
.
0 2
.
01
.
01
.
2
1
0 2
. 6 01
. 5 01
. 7
01
.
1 A =
, f =
.
01
. 3 0 2
. 8 01
. 9 0 2
. 1
1
01.1
01
.
0 2
.
01
.
8
1
Заметим, что в данном примере спектральный радиус r( ) A = 702
.
0
, а
.
3
41546595
.
3 31263729
точное решение x* =
. Здесь n=2, p=1 и для получения векторов
.
3 70159569
.
2
98449283
1
1 u ,v в качестве начального приближения выберем вектор x = . Тогда
0
0
0
1
1
получим следующие векторы u ,v :
0
0
340838
.
342103
.
3 30559
.
3 31776
. u =
, v =
.
0
369403
.
0
370814
.
2 97868
.
2 98907
.
95
Теперь по формулам
)
2
.
11
(
получим соответствующие приближения
“снизу” и “сверху” к точному решению * x уравнения
)
1
.
11
(
. Представим эти
приближения в виде следующей таблицы. Таблица 21 n
Итак, на 29-м шаге точность вычислений составляет 10-6, а на 40-м шаге
точность вычислений составляет уже 10-8. Отметим тот факт, что при
построении приближений, сходящихся к точному решению * x данного
примера, методом последовательных приближений точность 10-6 достигается
только на 45-м шаге.
96
Для сравнения построим в этом примере приближения методом
ускорения сходимости монотонных приближений (см.§2).
1
1
Здесь для определения векторов u ,v выберем вектор z = . Тогда по
0
0
0
1
1
алгоритму описанному в §2 , получим следующие векторы u ,v :
0
0
−5263
.
5263
.
−5263
.
5 263
. u =
, v =
.
0
−5263
.
0
5263
.
−5263
.
5263
.
Тогда по формулам
)
2
.
11
(
получим соответствующие приближения
“снизу” и “сверху” к точному решению * x уравнения
)
1
.
11
(
. Представим эти
приближения в виде следующей таблицы. Таблица 22
Номер
3 701595
.
3701596
.
2 984492
.
2 984493
.
Итак, на 40-м шаге точность вычислений составляет 10-6.
А теперь рассмотрим предложенный метод в случае “гибрида” методов
итеративного агрегирования и метода ускорения монотонных приближений
[73]. Следует отметить, что в этом случае, при помощи векторов u* v*
, , мы
можем получить лишь оценку точного решения * x .
Реализуем это на уже рассматриваемом здесь примере 1. Тогда здесь
векторы u ,v :
0
0
340838
.
342103
.
3 30559
.
3 31776
. u =
, v =
.
0
369403
.
0
370814
.
2 97868
.
2 98907
.
Приближения, полученные по формулам
)
2
.
11
(
представим в виде
следующей таблицы.
3 701595
.
3701595
.
2 984492
.
2 984492
.
Итак, здесь уже на 4-м шаге точность вычислений составляет 10-6, а на 8-
м шаге точность вычислений составляет уже 10-8. По сравнению с
предыдущими случаями, здесь заметно возросла скорость сходимости
приближений.
Проведем сравнительный анализ используемых в этом параграфе
численных методов при помощи следующего графика.
99
60
50
ий 40
вариант метода
ац
ускорения сходимости
т ер
и
метод ускорения
в о 30
сходимости
ст ч е
"гибрид" методов ОИА
ли 20
и метода ускорения
Ко
10
0
1
2
3
4
5
6
7
Порядок точности
Рис. 2. Сравнение варианта метода ускорения сходимости с другими
численными методами.
По предложенному методу автором разработана программа на языке
программирования TURBO PASCAL.
100 §12. Об одном варианте метода Зейделя
Балансовая модель производства является одной из наиболее простых
математических моделей. Она записывается в виде системы уравнений,
каждое из которых выражает требование равенства (баланса) между
количеством продукции, производимой отдельным экономическим объектом,
и совокупной потребностью в этом продукте. Балансовые модели
основываются на понятии межотраслевого баланса, который представляет
собой таблицу, характеризующую связи между отраслями (экономическими
объектами) экономической системы. В настоящее время большое число
работ посвящается этой модели и ее применению для решения различных
задач. Такой интерес к балансовой модели определяется тем, что, оказалось,
эта модель хорошо отражает многие существенные особенности
современного производства и в то же время легко поддается расчету. Во
многих странах мира балансовый метод используется для экономического
анализа, планирования и прогнозирования.
Система балансовых уравнений может быть записана в матричной
форме в виде следующего уравнения x=Ax+f.
Здесь используется терминология теории положительных операторов
[36].
Для того чтобы изложить суть предлагаемого варианта численного
метода предварительно опишем метод Зейделя и метод ускорения
сходимости приближений.
Одна из возможных интерпретаций метода Зейделя, изложенная в [16],
решения линейных алгебраических систем и более общих операторных
уравнений заключается в следующем. Если требуется решить уравнение
вида x = Ax + f ,
)
1
.
12
(
101
где x – неизвестный элемент некоторого банахова пространства Е, f –
заданный элемент из Е, А- линейный оператор, действующий в Е, то при
условии, что А=А1+А2
и в предположении, что существует оператор обратный к оператору (I-A1), уравнение
)
1
.
12
( , можно переписать в эквивалентном виде x = (I − A −1
) ⋅ A x + (I − A −1
) ⋅ f ,
)
2
.
12
(
1
2
1
после чего к полученному уравнению применить метод последовательных
приближений x
= I −
− A A x + I −
− A f m = , m 1
+
(
) 1
1
2 m
(
1 ) 1
,
(
,
1 ,...
2 )
который можно также записать в виде y
= A y
+ A y + f m = .
)
3
.
12
( m 1
+
1 m 1
+ m
(
,
1
2
)
,...
2
Т.е. по сути, применять метод последовательных приближений для
решения операторного уравнения вида x = Dx + h ,
)
4
.
12
(
где D = (I − A ) 1− ⋅ A , h = (I − A
.
1 )−1 ⋅ f
1
2
Именно такую интерпретацию допускает классический метод Зейделя
решения линейных систем алгебраических уравнений. Для того, чтобы этот
метод был реализуем, достаточно, чтобы число λ = 1 не являлось точкой
спектра оператора А1, а для этого, в частности, достаточно, чтобы спектральный радиус r(A1) оператора А1 удовлетворял неравенству r(A1)<1.
)
5
.
12
(
При этом для определенных классов операторов А такое преобразование
уравнения
)
1
.
12
(
(а именно, переход от уравнения
)
1
.
12
(
к вспомогательному и
эквивалентному уравнению
)
2
.
12
(
) обладает следующей полезной
особенностью: спектральный радиус оператора
−1
(I − A ) A , как было
1
2
установлено в [41], не больше, и, как правило, меньше спектрального радиуса r(A) оператора А в исходном уравнении
)
1
.
12
(
. А это, в частности,
обеспечивает,
вообще
говоря,
более
быструю
сходимость
102
последовательности {ym} к единственному решению * x уравнения
)
1
.
12
(
метода Зейделя
)
3
.
12
(
по сравнению с обычным методом последовательных
приближений x
= (A + A )x + f m = . m 1
+
1
2 m
(
,...
1
,
0
)
Более того, в этом случае удается получить явные оценки для эффекта
ускорения сходимости метода Зейделя по сравнению с обычным методом
последовательных приближений и указать другие алгоритмы построения еще
более быстро сходящихся приближений к неизвестному решению * x .
Рассмотрим уравнение
)
1
.
12
(
с матричным оператором А. В [41] было
установлено, что для уравнения
)
1
.
12
(
при условии
)
5
.
12
(
, метод Зейделя
монотонно зависит от выбора матрицы А1 , а именно, с возрастанием количества ненулевых элементов матрицы А1 скорость сходимости метода
)
3
.
12
(
возрастает, точнее говоря не уменьшается. Это можно
интерпретировать следующим образом: чем большую часть А1 матрицы А мы оставляем в обращаемой части
−1
(I − A ) уравнения, тем быстрее
1
приближения, полученные по методу Зейделя
)
3
.
12
(
, сходятся к решению * x .
Уместно, однако, сразу заметить при этом, что с «возрастанием» «доли» А1 , вообще говоря, усложняется процедура определения приближений по методу
Зейделя, эта процедура будет самой простой, если в качестве А1 брать «нижнюю» треугольную часть матрицы А, т.е. полагать i 1
− n y (m+ )1 = ∑a y(m+ )1 +∑a y(m) + f ,
= ,
1
)
6
.
12
( i ij j ij j i
(i n) j 1
= j=i
что как раз соответствует классической схеме метода Зейделя. Если же
«присоединить» к матрице А1 еще и главную диагональ, то в этом случае метод Зейделя примет несколько нетрадиционный вид: i n y(m+ )1 = ∑a y(m+ )1 + ∑a y(m) + f ,
= ,
1 ,
7
.
12
(
) i ij j ij j i
(i n) j 1
= j=i 1
+
т.е. примет вид неявной схемы, при которой для определения (m+1) – го
приближения по компоненте с номером i , т.е. при определении (m+ )1 y
нам i
103
придется решать для каждого i одно скалярное уравнение с неизвестным
(m+ )
1 y
. Этот метод назовем методом Зейделя первого порядка. i
Аналогичным образом определяются методы Зейделя второго и более
высоких порядков. Тем самым, чем «большая» часть матрицы А будет
включаться в А1 , тем сложнее будет фактически реализация метода Зейделя, т.к. с «ростом» матрицы А1 возрастает порядок системы уравнений, которую приходится решать для определения каждого следующего приближения, и
соответственно, усложняется схема реализации метода Зейделя.
В классической схеме метода Зейделя порядок соответствующей
системы фактически равен нулю.
Понятно, что применение неявных схем требует решения
вспомогательных систем линейных уравнений. Количество неизвестных в
этих системах прямо зависит от «порядка» метода Зейделя. Оно тем больше,
чем выше «порядок». В любом случае при применении метода Зейделя
«невысокого порядка», «порядок» соответствующей системы, вообще говоря,
меньше числа k – порядка исходной системы линейных алгебраических
уравнений, и потому применение соответствующей схемы является более
простым, нежели решение исходной системы n – уравнений с n –
неизвестными.
Итак, метод Зейделя осложняется в реализации с «ростом» матрицы А1 ,
и потому, естественно, на эту более сложную схему метода Зейделя имеет
смысл идти лишь в том случае, если при этом улучшается скорость
сходимости. Оказывается, что именно так и обстоит дело, что следует из
теоремы, доказанной в [41] и приведенной в монографии [36]. Теорема 12.1 . Пусть А≥θ, r(A)<1, и оператор А1 переводит каждый внутренний элемент конуса n R неотрицательных векторов
+ пространства n R во внутренний элемент. Тогда имеет место неравенство r[ (I − A )−1 A
1 2]<r(A).
На основании теоремы имеет место
104 Следствие .В условиях теоремы 12.1 метод Зейделя сходится быстрее, чем метод последовательных приближений, а метод
7
.
12
(
) сходится, вообще говоря, быстрее, чем метод
)
6
.
12
(
.
Суть излагаемого в данном параграфе варианта метода Зейделя, для
построения приближений, сходящихся к точному решению операторного
уравнения, состоит в том, что к полученному уравнению
)
4
.
12
(
предлагается
применить метод ускорения сходимости приближений, описанный в [36].
Изложим суть применяемого метода.
Рассмотрим операторное уравнение вида
)
4
.
12
(
. Предположим, что
спектральный радиус r(D) < 1; поэтому уравнение
)
4
.
12
(
имеет единственное
решение * x , которое является пределом последовательных приближений x
= Dx + , h (n =
,
1
,
0
,...)
2
n 1
+ n
при любом начальном приближении x ∈ E . Допустим, что начальное
0
приближение x = u выбрано так, что
0
0 u ≤ Du + . h
)
8
.
12
(
0
0
Тогда последовательные приближения u
= Du + h
)
9
.
12
(
n+1 n
будут удовлетворять соотношениям
* u ≤ u ≤ ... ≤ u ≤ u
≤ ... ≤ x .
)
10
.
12
(
0
1 n n 1
+
Аналогично, если начальное приближение x = v удовлетворяет
0
0
соотношению v ≥ Dv + h ,
)
11
.
12
(
0
0
то последовательные приближения v
= Dv + h
)
12
.
12
(
n+1 n
удовлетворяют соотношениям
* x ≤ ... ≤ v
≤ v ≤ ... ≤ v ≤ v .
)
13
.
12
(
n 1
+ n
1
0
Таким образом, если удается найти элементы u и v , удовлетворяющие
0
0
соответственно соотношениям
)
8
.
12
(
и
)
11
.
12
(
, то мы получаем монотонные
105
приближения к точному решению * x операторного уравнения
)
4
.
12
(
. Наличие
двусторонних монотонных приближений дает одновременно оценку
погрешности: если приближенным значениям решения * x считать элемент
1 (u +v то из
)
10
.
12
(
и
)
13
.
12
(
вытекает оценка n n ),
2
1
− (v − u ≤ u + v − x ≤ v − u
n n )
1 ( n n ) * 1 ( n n ).
2
2
2
Основную трудность составляет отыскание начальных приближений u
0
и v . В [36] указан алгоритм отыскания таких начальных приближений.
0
Изложим его суть.
Пусть z - внутренняя точка конуса K . Если r(D) < 1, то обязательно
0
найдется номер r , такой, что для данного вектора z обязательно будет
0
выполнено неравенство: D r z ≤ z
χ ,
0
0
где χ < 1. Тогда элемент
1
2
1−
1− r 1 z r
= χ z r
+ χ Dz + ... + D − z
1
0
0
0
удовлетворяет неравенству
1 Dz r
≤ χ z .
)
14
.
12
(
1
1
Не ограничивая общности можно считать, что z является внутренним
1
элементом конуса K . Поэтому для некоторого вещественного b > 0 будет
выполнено следующее неравенство:
1
1
− b 1
( r
− χ )z ≤ h ≤ b 1
( r
− χ )z .
)
15
.
12
(
1
1
Положим тогда u = bz
−
, v = bz .
0
1
0
1
Эти элементы удовлетворяют соотношениям
)
8
.
12
(
и
)
11
.
12
(
.
Действительно, в силу
)
14
.
12
(
1 / Du + h = b
− ⋅ Dz + h ≥ b r
− χ z + , h
0
1
1
и
)
8
.
12
(
вытекает из левой части неравенств
)
15
.
12
(
.
106
Аналогично
1
1
1 Dv + h = b ⋅ Dz + h ≤ b r
⋅ χ z + h ≤ b r
⋅ χ z + b 1
( r
− χ )z = v .
0
1
1
1
1
0
Конечно, в различных частных случаях элементы u и v можно
0
0
выбирать более простым способом. Например, если h ∈ K , то в качестве u ,
0
конечно, можно выбирать элемент h .
Пусть u и v удовлетворяют соответственно соотношениям
)
8
.
12
(
и
0
0
)
11
.
12
(
. Будем считать дополнительно, что выполнены неравенства u − u ≥ p v − v ,
)
16
.
12
(
1
0
1 ( 0
1 ) v − v ≥ q u − u ,
0
1
1 ( 1
0 )
где одно из чисел p и q положительно (при p = q = 0 эти неравенства
1
1
1
1
совпадают с
)
8
.
12
(
и
)
11
.
12
(
). Определим тогда элементы u + p v
*
1
1 1 u =
,
17
.
12
(
)
1
1+ p1 v + q u
*
1
1 1 v =
.
)
18
.
12
(
1
1+ q1 Теорема 12.2. Справедливы соотношения
*
*
* u ≤ u ≤ x ≤ v ≤ v .
вытекают
непосредственно из
17
.
12
(
) ,
)
18
.
12
(
и из неравенства Du + h ≤ Dv + h .
0
0
Очевидно,
1
*
* Du + h − u = D Du + h − u + p D Dv + h − v
1
1
[ ( 0
0 )
1
( 0
0 )]
1+ p1
и в силу
)
16
.
12
(
* Du + h − * u ≥ θ .
1
1
Это значит, что элемент * u удовлетворяет условию
)
8
.
12
(
. Как нам уже
1
известно, из этого условия вытекает, что *
* u ≤ x .
1
Аналогично
* v − Dv + h = D v − Dv − h + q D u − Du − h ≥ θ
1
( *1 ) 1 [ ( 0
0
) 1 ( 0
0
)] .
1+ q1
107
Значит, * v удовлетворяет
)
11
.
12
(
, и поэтому *
* v ≥ x .
1
1
Теорема доказана.
Формулы
17
.
12
(
) и
)
18
.
12
(
можно рассматривать как рекуррентный
процесс построения последовательностей * * u , v . Теорема 12.2 означает, что n n
этот рекуррентный процесс сходится не медленнее последовательностей
)
9
.
12
(
и
)
12
.
12
(
, и сохраняет монотонность последовательных приближений.
Многочисленные примеры показывают, что в достаточно общих
условиях процесс
17
.
12
(
) и
)
18
.
12
(
сходится существенно быстрее обычного
метода последовательных приближений.
Рассмотрим реализацию предложенного варианта метода Зейделя на
конкретных примерах. Пример 1. Пусть дано уравнение вида
)
1
.
12
(
, где
15
.
0
31
.
0
0 14
.
21
.
0
15
.
0
1
18
.
0
0 36
.
17
.
0
15
.
0
14
.
0
1
A =
19
.
0
0 16
.
21
.
0
25
.
0
18
.
0
, f = 1 .
27
.
0
0 14
.
0 12
.
13
.
0
24
.
0
1
33
.
0
0 22
.
21
.
0
2
.
0
19
.
0
2
9612529
.
454
9256427
.
474
Точное решение уравнения *
x =
4250761
.
468
, а спектральный радиус
8284457
.
433
3775432
.
545
r( ) A = 9975
.
0
.
При решении примера в данном случае метод Зейделя имеет «порядок
ноль».
Используя вышеизложенный метод ускорения сходимости, получим
приближения u* и v* . n n
Соответствующие приближения u* и v* , к координатам вектора n n
решения представим в виде таблицы.
108 Таблица 24 n
“ u*”
“ v* ” n n Приближения к 1-ой координате вектора решения
1 -31581.165783
33302.009434
541 2.457779
906.048065
1434 440.958437
468.920229
2009 453.467382
456.450447
2957 454.923932
454.998456
4196 454.960952
454.961552
5000 454.961239
454.961266 Приближения к 2-й координате вектора решения
1 -32943.148882
34738.487582
541 2.744047
945.628970
1434 460.313883
489.491656
2009 473.366807
476.479597
2957 474.886699
474.964463
4196 474.925329
474.925955
5000 474.925629
474.925656 Приближения к 3-й координате вектора решения
1 -32450.640618
34219.583220
541 3.251564
932.142260
1434 454.030183
482.774902
2009 466.889377
469.955967
2957 468.386711
468.463321
4196 468.424767
468.425384
5000 468.425062
468.425089 Приближения к 4-й координате вектора решения
1 -29994.511930
31630.236737
541 3.465972
862.843575
109
1434 420.510788
447.104409
2009 432.407670
435.244773
2957 433.792951
433.863828
4196 433.828160
433.828730
5000 433.828433
433.828458 Приближения к 5-й координате вектора решения
1 -37631.653423
39686.310105
541 5.420638
1083.643995
1434 528.668463
562.034312
2009 543.594958
547.154547
2957 545.333010
545.421936
4196 545.377184
545.377900
5000 545.377527
545.377558
Проиллюстрируем данные вычисления при помощи следующего
графика.
7000
6000
5000
ий ац т ер 4000
и в о ст 3000
ч е ли Ко 2000
1000
0
1
2
3
4
5
6
7
Порядок точности
Рис.3. Вариант метода Зейделя (порядок «0»).
110
Рассмотрим теперь применение предложенного варианта метода Зейделя
в случае, когда метод Зейделя имеет «порядок один». Реализуем этот случай
на вышеизложенном примере.
Необходимые начальные условия полностью совпадают с начальными
условиями в рассмотренном выше примере.
Используя вышеизложенный метод ускорения сходимости, получим
приближения u* и v* . n n
Соответствующие приближения u* и v* , к координатам вектора n n
решения представим в виде таблицы. Таблица 25 Приближения к 1-ой координате вектора решения
Номер
приближе
“ u*”
“ v* ” n n
ний
n
1 -19145.167945
20488.931731
363 20.887959
887.679663
1185 451.585334
458.327096
1957 454.926203
454.996660
3312 454.961474
454.961498 Приближения к 2-ой координате вектора решения
1 -19935.975115
21336.627643
363 22.692057
925.744732
1185 471.407031
478.430825
1957 474.887660
474.961064
3312 474.924407
474.924432 Приближения к 3-ой координате вектора решения
1 -19650.507350
21031.240179
363 22.616370
912.839387
111
1185 464.956456
471.880463
1957 468.387635
468.459997
3312 468.423861
468.423885 Приближения к 4-ой координате вектора решения
1 -18159.668279
19436.269267
363 21.358973
845.007810
1185 430.619226
437.025430
1957 433.793809
433.860760
3312 433.827326
433.827348 Приближения к 5-ой координате вектора решения
1 -22790.544091
24396.542036
363 28.279619
1060.858104
1185 541.354262
549.385486
1957 545.334120
545.418054
3312 545.376139
545.376167
Как видно из последней таблицы, по сравнению с предыдущим случаем
несколько возросла скорость сходимости приближений u* и v* к точному n n
решению.
Отметим также тот факт, что основные вычисления по предложенному
варианту метода Зейделя получены с помощью разработанной автором
программы на языке программирования TURBO PASCAL
112 ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ
Проведенные в диссертационной работе исследования направленные на
разработку новых методов решения операторных уравнений, описывающих
экономические модели (модель межотраслевого баланса). Получены
следующие научные и практические результаты.
1. Разработан и апробирован на большом количестве примеров
итерационный метод решения системы линейных алгебраических уравнений
вида x = Ax + f с квадратной матрицей A , в случае, когда наибольшее по
модулю собственное значение матрицы A , больше чем единица.
2. Предложен метод получения двусторонних оценок точного решения
* x операторного уравнения вида x = Ax + f , в случае, когда спектральный
радиус не обязательно меньше единицы, а также подходы к уточнению
полученных
оценок.
Метод
проиллюстрирован
соответствующими
примерами.
3. Получен синтез методов ускорения сходимости монотонных
приближений
к
решению
* x
уравнения
вида x = Ax + f
и
однопараметрического итеративного агрегирования.
4. Предложен вариант метода ускорения сходимости монотонных
приближений к решению уравнения вида x = Ax + f , в котором упрощена
задача поиска начальных приближений.
5. Разработан и апробирован на большом количестве примеров вариант
метода Зейделя, позволяющий строить двусторонние приближения к
точному решению уравнения вида x = Ax + f .
6. Составлена библиотека программ на языке программирования TURBO
PASCAL, которая позволяет реализовывать полученные в данной работе
методы и алгоритмы.
Таким образом:
113
- Разработаны новые методы решения операторных уравнений,
описывающих экономические модели (модель межотраслевого баланса),
обладающих высокой скоростью сходимости последовательностей к точному
решению данных уравнений, а также способностью сходится к точному
решению даже в тех случаях, когда спектральный радиус оператора больше
единицы.
- Разработан комплекс программ на языке программирования TURBO
PASCAL, реализующих эти алгоритмы.
114 Литература.
1. Архангельский, Ю.С. Численные исследования методов итеративно-
го агрегирования для решения задачи межпродуктового баланса /Ю.С. Архангельский, И.А. Вахутинский, Л.М. Дудкин и др. //Автоматика и телемеханика. - 1975. - №7. - С.75-82.
2. Ашманов, С.А. Введение в математическую экономику /С.А. Ашма-
нов. – М.:Наука, 1984. – 296с.
3. Бабаджанян, А.А. О скорости сходимости метода однопараметриче-
ского итеративного агрегирования/А.А. Бабаджанян //Автоматика и телемеханика. - 1982. - №11. - С.171-173.
4. Бахвалов Н. Численные методы /Н. Бахвалов, Н. Жидков, Г. Кобель-
ков - М.: Лаборатория Базовых Знаний, 2000. – 624 c.
5. Бахтин, И.А. Исследование уравнений с положительными операто-
рами: Дис. … д-ра физ.-мат. наук /И.А. Бахтин. - Ленинград, 1967. – 320с.
6. Бахтин, И.А. Метод последовательных приближений в теории урав-
нений с вогнутыми операторами /И.А. Бахтин, М.А. Красносельский // Сибирский математический журнал . - 1961.- Т.2, № 3.- С.313-330.
7. Бахтин, И.А. О непрерывности положительных операторов /И.А.
Бахтин, М.А. Красносельский, В.Я. Стеценко // Сибирский матема- тический журнал . - 1962.- Т.3, № 1.- С.8-17.
8. Беллман Р. Квазилинеаризация и нелинейные краевые задачи /Р.
Беллман, Р. Калаба. – М.: Мир, 1968. – 270с.
9. Вен, В.Л. Некоторые вопросы агрегирования линейных моделей
/В.Л. Вен, А.И. Эрлих //Известия АН СССР. Сер. техническая ки- бернетика. – 1970.- №5. - С.3-8.
10. Вержбицкий, В.М. Численные методы (линейная алгебра и нели-
нейные уравнения): Учеб. Пособие для вузов /В.М. Вержбицкий. – М.: Высш. шк., 2000. – 266 с.
11. Вулих, Б.З. Введение в теорию полуупорядоченных пространств
/Б.З. Вулих. – М.: Наука, 1961. – 407 с.
12. Вулих, Б.З. Введение в функциональный анализ /Б.З. Вулих. – М.:
Физматгиз, 1967.– 415с.
13. Вулих, Б.З. Специальные вопросы геометрии конусов в нормиро-
ванных пространствах: Учебное пособие /Б.З. Вулих. – Калинин: Издательство калининского университета, 1978. – 84 с.
14. Гантмахер, Ф.Р. Теория матриц /Ф.Р. Гантмахер. – М: Наука, 1966. –
576с.
15. Гробова, Т.А. О методе однопараметрического итеративного агре-
гирования для решения систем линейных и нелинейных алгебраиче- ских уравнений, интегральных уравнений /Т.А. Гробова
115
//Ставропольский государственный университет, Ставрополь, 2001. – 24с. - Деп. в ВИНИТИ 19.11.01 №2392 – В2001.
16. Гробова, Т.А. Об одном новом варианте метода Зейделя /Т.А. Гро-
бова //Научно-методическая конф. преподавателей и студентов «XXI век – век образования». Материалы 46 научно-метод. конф. преподавателей и студентов «XXI век – век образования». – Ставро- поль, 2001. – С.4-9.
17. Гробова, Т.А., Об одном аналоге метода однопараметрического
итеративного агрегирования /Т.А. Гробова, В.Я. Стеценко //Вестник СГУ. -2001. - Выпуск 28. – С.12-16.
18. Гробова, Т.А. Об одной новой схеме реализации вариантов метода
Зейделя /Т.А. Гробова, В.Я. Стеценко // Вестник молодых ученых. - Санкт – Петербург, 2001. – С.34-39.
19. Данфорд Н., Шварц Дж. Линейные операторы. Общая теория /Н.
Данфорд, Дж. Шварц. – М.: Иностранная литература, 1962. – 895c.
20. Демиденко, Н.А. Применение метода итеративного агрегирования к
расширенной модели межотраслевого баланса /Н.А. Демиденко //Экономика и математические методы. – 1977. - Т.13, №3. - С.594- 598.
21. Дудкин, Л.М. Межотраслевой баланс и материальные балансы от-
дельных продуктов /Л.М. Дудкин, Э.Б. Ершов // Плановое хозяйст- во. – 1965. - №5. - С.59-63.
22. Есаян, А.Р. Локализация спектра линейного оператора /А.Р. Есаян,
В.Я. Стеценко //Междунар. Конгресс математиков (1966; Москва). Тезисы кр. науч. сообщений Междунар. Конгресса математиков. Секция 5. – М., 1966. – С.45-74.
23. Есаян, А.Р. О разрешимости уравнений второго рода /А.Р. Есаян,
В.Я. Стеценко // Труды семинара по функциональному анализу. Во- ронежский гос. ун-т. – Воронеж, 1963. – Вып. 7. – С.36-41.
24. Есаян, А.Р. Оценки спектра интегральных операторов и бесконеч-
ных матриц /А.Р. Есаян, В.Я. Стеценко // Докл. АН СССР. – 1964. – Т. 157, №2. – С.12-19.
25. Итеративное агрегирование и его применение в планировании /Под
ред. Л.М. Дудкина. – М.: Экономика, 1979. – 328 с.
26. Канторович, Л.В. Функциональные анализ в нормированных про-
странствах /Л.В. Канторович, Г.П. Акилов. – М.: Наука, 1977. – 496 с.
27. Канторович, Л.В. Функциональный анализ в полуупорядоченных
пространствах /Л.В. Канторович, Б.З. Вулих, А.Г. Пинскер. - М.: Физматгиз, 1959. - 684 с.
28. Канторович, Л.В. Приближенные методы высшего анализа /Л.В.
Канторович, В.И. Крылов. – М.-Л.: Физматгиз, 1962. – 708с.
116
29. Коллатц Л. Функциональный анализ и вычислительная математика
/Л. Коллатц. - М.: Мир, 1969. - 421с.
30. Колмогоров, А.Н. Элементы теории функций и функционального
анализа /А.Н. Колмогоров, С.В. Фомин. - М.: Наука, 1981. - 543с.
31. Коршунова Н. Математика в экономике /Н. Коршунова, В. Плясу-
нов. – М.:Издательство «Вита-Пресс», 1996. – 368с.
32. Костенко, Т.А. К вопросу о существовании и единственности реше-
ния операторного уравнения, нелинейного относительно параметра
λ. /Т.А. Костенко// «Международная школа-семинар по геометрии и анализу памяти Н.В. Ефимова» (1998; Ростов-на-Дону). Тезисы док- ладов «Междунар. школы-семинара по геометрии и анализу памяти Н.В. Ефимова» (5-11 сент., 1998г.). – Ростов-на-Дону, 1998. – С.104- 105.
33. Костенко, Т.А. О разрешимости операторных уравнений второго
рода с линейными и нелинейными операторами /Т.А. Костенко // «Проблемы физико-математических наук», науч.-метод. конф. пре- подавателей и студентов «Университетская наука – региону» (43; 1998; Ставрополь). Материалы XLIII науч.-метод. конф. преподава- телей и студентов «Университетская наука – региону». – Ставро- поль, 1998. – С.111-122.
34. Красносельский, М.А. Положительные решения операторных урав-
нений /М.А. Красносельский. – М.: Физматгиз, 1962. – 394с.
35. Красносельский, М.А. Правильные и вполне правильные конусы
/М.А. Красносельский // Докл. АН СССР.-1960. - Т.135. - № 2. – С.241-255.
36. Красносельский, М.А. Приближенное решение операторных урав-
нений /М.А. Красносельский, Г.М. Вайникко, П.П. Забрейко и др. – М: Наука, 1969. – 456с.
37. Красносельский, М.А. Геометрические методы нелинейного анализа
/М.А. Красносельский, П.П. Забрейко. - М.: Наука, 1965. - 624с.
38. Красносельский, М.А. Позитивные линейные системы: метод поло-
жительных операторов /М.А. Красносельский, Е.А. Лифшиц, В.И. Соболев. – М: Наука, 1985. – 256с.
39. Красносельский, М.А. Положительно обратимые линейные опера-
торы и разрешимость линейных уравнений /М.А. Красносельский, Е.А. Лифшиц, В.В. Покорный, В.Я. Стеценко // Докл. АН Таджик- ской ССР. -1974. - Т.XVII, № 1. - С.12-15.
40. Красносельский, М.А. О сходимости метода однопараметрического
агрегирования /М.А. Красносельский, А.Ю. Островский, А.В. Собо- лев // Автоматика и телемеханика. – 1978. - №9. - С.102-109.
117
41. Красносельский, М.А. Замечания о методе Зейделя /М.А. Красно-
сельский, В.Я. Стеценко // Журнал вычислительной математики и математической физики. – 1969. - Т.9, №1. - С.177-182.
42. Крейн, М.Г. Линейные операторы, оставляющие инвариантным ко-
нус в пространстве Банаха /М.Г. Крейн, М.А. Рутман // Успехи ма- тематических наук. - 1948. – Т.1, №3. - С.3-95.
43. Крукиер, Л.А. Численные методы решения задач конвекции-
диффузии со смешанными производными /Л.А. Крукиер, Т.С. Мар- тынова. – г. Ростов-на –Дону: Изд-во РГУ, 2003. -156с.
44. Кубекова, Б.С. Об уточнении оценок решения операторного уравне-
ния в полуупорядоченном пространстве с u0–ограниченным снизу оператором /Б.С. Кубекова // «Понтрягинские чтения –XI», науч. конф. (2000; Воронеж). Тезисы докладов науч. конф. «Понтрягин- ские чтения –XI» (3-9 мая, 2000г.). – Воронеж, 2000. – С.95-98.
45. Кубекова, Б.С. Отыскание приближений по недостатку и по избытку
к решению операторного уравнения с монотонно разложимым опе- ратором /Б.С. Кубекова //«Математическое моделирование в науч- ных исследованиях», Всероссийская науч. конф. (2000). Тезисы докладов Всероссийской науч. конф. «Математическое моделирова- ние в научных исследованиях» (21-30 сент., 2000г.). – Ставрополь, 2000.– С.47-49.
46. Кубекова, Б.С. О методе однопараметрического итеративного агре-
гирования /Б.С. Кубекова, В.Я. Стеценко, Т.А. Гробова //«Математика. Компьютер. Образование», междунар. конф. (8; 2001; Пущино). Тезисы докладов восьмой междунар. конф. «Мате- матика. Компьютер. Образование» (31 янв. – 5 февр., 2001г.).– Пу- щино, 2001. - С.230-232.
47. Кубекова, Б.С. Об одном методе построения двусторонних прибли-
жений к решению операторного уравнения с монотонно разложи- мым оператором /Б.С. Кубекова, В.Я. Стеценко, М.Н. Павлова //Журнал вычислительной математики и математической физики.– 2001.– Т.41, № 6. – С.846-854.
48. Кузнецов, Ю.А. К теории итерационных процессов /Ю.А. Кузнецов
//Докл. АН СССР. – 1969. - Т.184, №4, -С.863-866.
49. Леонтьев, В.В. Экономика и математические методы /В.В. Леонтьев,
Д. Форд. – М: Наука, 1972. – 242с.
50. Лифшиц, Е.А. К теории полуупорядоченных банаховых пространств
/Е.А. Лифшиц // Функциональный анализ и его приложения, 1969. - Т.3, №1. - С.91–92.
51. Люстерник, Л.А. Элементы функционального анализа /Л.А. Люс-
терник, В.И. Соболев. – М: Наука, 1965. – 520с.
118
52. Моришима М. Равновесие, устойчивость, рост /М. Моришима. - М.:
Наука, 1972. - 179с.
53. Никайдо Х. Выпуклые структуры и математическая экономика /Х.
Никайдо. - М.: Мир, 1972. - 518с.
54. Ортега Дж. Итерационные методы решения нелинейных систем
уравнений со многими неизвестными /Дж. Ортега, В. Рейнболдт. - М.: Мир, 1975. - 327с.
55. Островский, А.Ю. О сходимости монотонных итерационных про-
цессов /А.Ю. Островский //Журнал вычислительной математики и математической физики. – 1977. - Т. 17, №1. - С.233-238.
56. Пароди М. Локализация характеристических чисел матриц и ее
применения /М. Пародии. - М.: Иностранная литература, 1960. - 270с.
57. Плюта, А.И. Об одном варианте метода ускорения сходимости
монотонных
приближений
к
решению
уравнения
вида x = Ax + f /А.И. Плюта //«Теоретические и прикладные проблемы
современной физики», региональная науч. конф. (2002; Ставрополь). Материалы региональной науч. конф. «Теоретические и прикладные проблемы современной физики». – Ставрополь, 2002. – С.255-262.
58. Плюта, А.И. О некоторых методах получения оценок точного ре-
шения * x операторных уравнений вида x = Ax + f в случае, когда
спектральный радиус ρ( ) A не обязательно меньше единицы /А.И.
Плюта //«Итерационные методы и матричные вычисления», Меж- дународная летняя школа молодых ученых. -Ростов-на-Дону, 2002. – С.482-486.
59. Плюта, А.И. «Гибрид» методов ускорения сходимости монотонных
приближений к решению уравнения вида x = Ax + f и однопарамет- рического итеративного агрегирования /А.И. Плюта, В.Я. Стеценко //Ученые
записки
/Ставропольский
гос.
ун-т,
физико-
математический факультет. – Ставрополь, 2002. – С.79-85.
60. Плюта, А.И. Об одном варианте метода Зейделя /А.И. Плюта, В.Я.
Стеценко //Математическое моделирование. – Москва. – 2003г. – Т.15, №12. - С.29-36
61. Радченко, В.В. Применение метода Ньютона-Канторовича для рас-
чета нелинейного межотраслевого баланса /В.В. Радченко, В.Я. Сте- ценко // Модели и методы экономических целенаправленных сис- тем.- Новосибирск, 1977. - С.160-166.
62. Самарский, А.А. Численные методы /А.А. Самарский, А.В. Гулин –
М.: Наука, 1989. – 187с.
63. Стеценко, В.Я. Исследование сходимости метода многопараметри-
ческого итеративного агрегирования при решении линейных алгеб- раических систем и интегральных уравнений /В.Я. Стеценко
119
//«Теория и практика использования методов агрегирования в пла- нировании и управлении», совещание (Киев). Материалы совещания «Теория и практика использования методов агрегирования в плани- ровании и управлении». – Киев, 1984. – С. 74-81.
64. Стеценко, В.Я. Исследования по теории положительных операторов
в пространствах с конусом: Дисс. … д-ра физ.-мат. наук /В.Я. Сте- ценко. – Воронеж, 1968. – 307с.
65. Стеценко, В.Я. Об одном методе ускорения сходимости итерацион-
ных процессов /В.Я. Стеценко //Докл. АН СССР. – 1968. – Т.178, №3. - С.1021-1024.
66. Стеценко, В.Я. Элементы теории полуупорядоченных пространств.
Приближенное решение операторных уравнений: Учеб. пособие /В.Я. Стеценко, В.А. Галкина. – Ставрополь: Изд-во СГУ, 1998. – 168c.
67. Стеценко, В.Я. О методе однопараметрического итеративного агре-
гирования для нелинейных уравнений /В.Я. Стеценко, Т.А. Гробова // Воронежская зимняя математическая школа: Тезисы докладов. - Воронеж, 2001.- С.254-256.
68. Стеценко, В.Я. Квалифицированные двусторонние оценки для спек-
трального радиуса линейного положительного оператора /В.Я. Сте- ценко, Т.А. Костенко //Ставропольский государственный универси- тет, Ставрополь. - 1997. – 13с. Деп. в ВИНИТИ 14.11.97 №3321 – В97.
69. Стеценко, В.Я. Метод ускорения сходимости приближений к спек-
тральному радиусу линейного положительного оператора и к реше- нию линейного операторного уравнения /В.Я. Стеценко, Т.А. Кос- тенко //Вестник СГУ. -1999. - Вып. 20. - С.3-13.
70. Стеценко, В.Я. Новые оценки сверху спектрального радиуса мат-
ричных и интегральных операторов /В.Я. Стеценко, Л.Н. Кириллова, А.И. Плюта //«Международная школа-семинар по геометрии и ана- лизу памяти Н.В. Ефимова» (2002; Ростов-на-Дону). Труды участ- ников «Междунар. школы-семинара по геометрии и анализу памяти Н.В. Ефимова». – Ростов-на-Дону, 2002.-С.160-161.
71. Стеценко, В.Я. Методы ускорения при отыскании спектрального ра-
диуса линейного оператора и решении линейного операторного уравнения /В.Я. Стеценко, Т.А. Костенко //«Международная школа- семинар по геометрии и анализу памяти Н.В. Ефимова» (1998; Рос- тов-на-Дону). Тезисы докладов «Междунар. школы-семинара по геометрии и анализу памяти Н.В. Ефимова» (5-11 сент., 1998г.). – Ростов-на-Дону, 1998. – С.124-126.
120
72. Стеценко, В.Я. Обзор и реализация на ЭВМ методов решения сис-
тем линейных и нелинейных уравнений: Учебное пособие /В.Я. Стеценко, А.И. Плюта. – Ставрополь: Изд-во СГУ, 2003.-71с.
73. Стеценко, В.Я. О некоторых методах построения монотонных при-
ближений к решению линейных операторных уравнений /В.Я. Сте- ценко, А.И. Плюта //«Теоретические и прикладные проблемы со- временной физики», региональная науч. конф. (2000; Ставрополь). Материалы региональной науч. конф. «Теоретические и приклад- ные проблемы современной физики». – Ставрополь, 2002.-С.281- 284.
74. Стеценко, В.Я. Об одном итерационном методе решения систем
линейных алгебраических уравнений вида x = Ax + f с квадратной матрицей A /В.Я. Стеценко, А.И. Плюта //«Современные методы теории функций и смежные проблемы», конф. (2003; Воронеж). Ма- териалы конф. «Современные методы теории функций и смежные проблемы»– Воронеж, 2003. -С.250-251.
75. Фаддеев, Д.К. Сборник задач по высшей алгебре /Д.К. Фаддеев, И.
С. Соминский. – М.: Наука, 1964. – 304с.
76. Фаддеев, Д.К. Вычислительные методы линейной алгебры /Д.К.
Фаддеев, В.Н. Фаддеева. – М.: Физматгиз, 1960. - 656с.
77. Форсайт Дж. Численное решение систем линейных алгебраических
уравнений /Дж. Форсайт, К. Молер. – М.: Мир, 1969. – 354с.
78. Функциональный анализ /Под ред. С.Г. Крейна. – М.: Наука, 1972. –
544с.
79. Хомяков, В.А. Обобщение одного доказательства сходимости про-
цесса итеративного агрегирования для решения систем линейных уравнений /В.А. Хомяков // Автоматика и телемеханика. – 1973.- №7. – С.15-23.
80. Шаабан М. Обобщенная норма интегральных операторов и матриц
/М. Шаабан //Изв. АН Таджикской ССР. – 1998. – Т.108, №2. – С.3- 12.
81. Щенников, Б.А. Метод агрегирования для решения систем линей-
ных уравнений /Б.А. Щенников // Докл. АН СССР.- 1967.- Т.173, №4. С.781-784.
82. Щенников, Б.А. Применение метода итеративного агрегирования
для решения систем линейных уравнений /Б.А. Щенников // Эконо- мика и математические методы. – 1966. – Т.2, №5. - С.723-731.
121 ПРИЛОЖЕНИЕ
§1. Метод последовательных приближений.
program wer2; var e,k,k1,m1,l,k0,r,max1,max2,k2,k3,k4,k5,max3:real; i,p,m,m01,m2,n:integer; a: array [1..30,1..30] of real; x,b,c,c1,t,c2,t1,c3,t2: array [1..30] of real; procedure wwodm; var i,j: integer; begin writeln('Введите размерность матрицы А:'); readln(n); for i:=1 to n do begin for j:=1 to n do begin write('введите элемент матрицы A[ ',i,',',j,']='); readln(a[i,j]); end; end; end; procedure wwodv; var i:integer; begin writeln('введите координаты свободного вектора f:'); for i:=1 to n do readln(b[i]); end; procedure wwodp; var i:integer; begin writeln('введите координаты начального приближения Х:'); for i:=1 to n do readln(x[i]); writeln('введите необходимую точность вычислений E:'); readln(e); end; procedure umnog; var i,j: integer; begin for i:=1 to n do begin l:=0; for j:=1 to n do begin l:=a[i,j]*x[j]+l;
122
end; c[i]:=l+b[i]; { writeln(c[i]);} end; { for i:=1 to n do begin g[i]:=c[i]+b[i]; end}; end; procedure vivod; var i: integer; begin for i:=1 to n do write(c[i]:11:8,' '); end; procedure usl1; var i,j: integer; begin for i:=1 to n do begin r:=0; for j:=1 to n do begin r:=abs(a[i,j])+r; end; c1[i]:=r; {writeln(c1[i]:3:3);} end; max1:=c1[1]; for i:=2 to n do begin if c1[i]>max1 then max1:=c1[i]; end; { writeln(max1:3:3);} if max1<1 then begin writeln('первое условие выполняется'); umnog; for i:=1 to n do begin t[i]:=c[i]-x[i]; { writeln(t[i]);} end; m1:=t[1]; for i:=2 to n do begin if abs(t[i])>m1 then m1:=abs(t[i]); end; {writeln(m1);} m:=trunc(ln((e*(1-(max1)))/m1)/(ln(max1)))+1; {writeln(m);} end else writeln('первое условие не выполняется'); end; procedure usl2; var i,j: integer;
123
begin for i:=1 to n do begin k:=0; for j:=1 to n do begin k:=abs(a[j,i])+k; end; c2[i]:=k; {writeln(c2[i]:3:3);} end; max2:=c2[1]; for i:=2 to n do begin if c2[i]>max2 then max2:=c2[i]; end; {writeln(max2:3:3);} if max2<1 then begin writeln('выполняется второе условие'); umnog; for i:=1 to n do begin t1[i]:=c[i]-x[i]; {writeln(t1[i]:3:3);} end; k1:=0; for i:=1 to n do begin k1:=k1+t1[i]; end; m01:=trunc((ln((e*(1-max2))/abs(k1)))/(ln(max2)))+1; {writeln(m01:3);} end else writeln('второе условие не выполняется'); end; procedure usl3; var i,j:integer; begin for i:=1 to n do begin k2:=0; for j:=1 to n do begin k2:=sqr(a[i,j])+k2; end; c3[i]:=k2; { writeln(c3[i]:3:3);} end; k3:=0; for i:=1 to n do begin k3:=k3+c3[i]; end; max3:=sqrt(k3); {writeln(max3:3);} if max3<1 then begin writeln('третье условие выполняется'); umnog; for i:=1 to n do begin t2[i]:=c[i]-x[i]; {writeln(t2[i]:3:3);} end; k4:=0; for i:=1 to n do begin k4:=sqr(t2[i])+k4; end;
124
k5:=sqrt(k4); m2:=trunc((ln((e*(1-max3))/k5))/(ln(max3)))+1; writeln(m2:3); end else writeln('третье условие не выполняется'); end; begin {основная программа} wwodm; wwodv; wwodp; umnog; usl1; usl2; usl3; p:=m2; readln; {writeln(m);} for i:=1 to p do begin umnog; write( i,':'); vivod; x:=c; writeln; readln; end; readln; end.
125
§2. Метод ускорения сходимости монотонных приближений к решению уравнения вида x = Ax + f (r( ) A < )
1 .
program wert; var ch,ch1,zn,zn1,f,z0,z01,z1,a1,a2,a00,b00,b0,u0,v0,u,v,p0,q0,u2,v2,u02,c72,p1,q1,u 1,v1: array[1..25] of real; a: array[1..25,1..25] of real; h1,h2,h01,h02,h11,h12,h101,h102,s,k,b,t,k1,d0,d1,d01,d10,m01,m02,d02,d12,d01 2,d102,k0:real; c,n1,i,j,n,q,l,i1 :integer; procedure wwod; var i,j:integer; begin writeln('введите размерность матрицы A:'); readln(n); writeln('Ввод элементов матрицы А:'); for i:=1 to n do begin for j:=1 to n do begin write('элемент A[',i,',',j,']='); readln(a[i,j]); end; end; writeln('Введите координаты свободного вектора f:'); for i:=1 to n do begin readln(f[i]); end; end; procedure byferr; var i,j:integer; begin for i:=1 to n do begin z01[i]:=z0[i]; { writeln(u01[i]:4:4)} end; end; procedure umn; var i,j: integer; s: real; begin for i:=1 to n do begin s:=0; for j:=1 to n do begin s:=a[i,j]*z01[j]+s; end; a1[i]:=s;
126
end; end; procedure vich; var i,j:integer; begin for i:=1 to n do begin d0:=0; d1:=0; for j:=1 to n do begin d01:=a[i,j]*u0[j]; d0:=d0+d01; d10:=a[i,j]*v0[j]; d1:=d10+d1; end; u[i]:=d0+f[i]; v[i]:=d1+f[i]; end; end; procedure otn; var i,j:integer; begin for i:=1 to n do begin zn[i]:=v0[i]-v[i]; ch[i]:=u[i]-u0[i]; {writeln(u[i]:5:5);} end; h2:=zn[1]; for i:=2 to n do begin if zn[i]>h2 then h2:=zn[i]; end; { writeln(h2:6:6);} h1:=ch[1]; for i:=2 to n do begin if ch[i]<h1 then h1:=ch[i]; end; {writeln(h1:8:8); } m01:=h1/h2; {writeln(m01:8:8);} h01:=zn[1]; for i:=2 to n do begin if zn[i]<h01 then h01:=zn[i]; end; h02:=ch[1]; for i:=2 to n do begin if ch[i]>h02 then h02:=ch[i]; end; m02:=h01/h02; { writeln(m02:8:8); } end; procedure byferr2;
127
var i,j : integer; begin for i:=1 to n do begin u2[i]:=u[i]; v2[i]:=v[i]; u02[i]:=u0[i]; c72[i]:=v0[i]; p1[i]:=p0[i]; q1[i]:=q0[i]; end; end; begin {начало основной программы} wwod; writeln('Введите начальные векторы:'); writeln('вектор u0:'); for i:=1 to n do readln(u0[i]); writeln('вектор v0:'); for i:=1 to n do readln(v0[i]); writeln('Введите количество приближений:'); readln(q); for l:=1 to q do begin vich; otn; { writeln(m01:5:5);} for i:=1 to n do begin u1[i]:=(u[i]+m01*v[i])/(1+m01); v1[i]:=(v[i]+m02*u[i])/(1+m02); writeln(l,':',u1[i]:11:8,' ',v1[i]:11:8); end; for i1:=1 to n do begin u0[i1]:=u[i1]; v0[i1]:=v[i1]; end; readln; end; end.
128 §3. Метод однопараметрического итеративного агрегирования решения линейных операторных уравнений вида x = Ax + f , где оператор A - матрица n - го порядка.
program wert; type Mat = Array[1..30,1..30] of real; Vec = Array[1..30] of real; var z : Mat; f,l,x,s,a,y :Vec; m,m1,g,g1,u,u1,h,h1,t:real; r,i,j,k,p,k1 : integer; procedure wwodmatr; var i,j:integer; begin for i:=1 to p do begin for j:=1 to p do begin write('Введите элемент матрицы А[',i,',',j,']='); readln(z[i,j]); end; end; end; procedure wwodf; var i:integer; begin writeln('Введите координаты свободного вектора f:'); for i:=1 to p do readln(f[i]); end; procedure wwodl; var i: integer; begin for i:=1 to p do l[i]:=1; end; procedure wwodx; var i:integer; begin writeln('Введите координаты вектора x (начального приближения) :'); for i:=1 to p do readln(x[i]); end; procedure umnog; var i,j : integer; begin
129
for i:=1 to p do begin m:=0; for j:=1 to p do begin m1:=z[i,j]*x[j]; m:=m1+m; end; s[i]:=m; end; end; procedure scalf; var i :integer; begin g:=0; for i:=1 to p do begin g1:=f[i]*l[i]; g:=g+g1; end; end; procedure scalx; var i:integer; begin h:=0; for i:=1 to p do begin h1:=x[i]*l[i]; h:=h+h1; end; end; procedure scalAx; var i: integer; begin u:=0; for i:=1 to p do begin u1:=s[i]*l[i]; u:=u1+u; end; end; procedure ttt; var t: real; begin t:=g/(h-u); end; procedure rrr ; var i: integer; begin for i:=1 to p do a[i]:=s[i]*t; end; procedure summ;
130
var i: integer; begin for i:=1 to p do y[i]:=a[i]+f[i]; end; procedure wewod; var i: integer; begin for i:=1 to p do write(y[i]:11:8,' '); end; begin { основная программа } writeln('Решение линейного уравнения вида x=Ax+f'); writeln('Введите размерность матрицы А:'); readln(p); wwodmatr; wwodf; wwodl; wwodx; scalf; writeln('ВВЕДИТЕ КОЛИЧЕСТВО ИТЕРАЦИЙ:'); readln(r); for k:=1 to r do begin umnog; scalx; scalAx; t:=g/(h-u); rrr; summ; write(k,':'); wewod; for k1:=1 to p do x[k1]:=y[k1]; writeln; end; writeln('Итак, на ',r,'-м шаге мы получили приближения к решению'); writeln('линейного уравнения вида x=Ax+f'); readln; end.
131 §4. Метод однопараметрического итеративного агрегирования решения нелинейных операторных уравнений вида x = F(x) + f , где F(x) - нелинейный оператор.
program wert; type Mat = Array[1..30,1..30] of real; Vec = Array[1..30] of real; var z,k1,x1 : Mat; f,l,x,s,a,y :Vec; m,m1,g,g1,u,u1,h,h1,t:real; r,i,j,k,p,k2 : integer; procedure wwodmatr; var i,j:integer; begin writeln('Ввод коэффициентов при неизвестных переменных системы:'); for i:=1 to p do begin for j:=1 to p do begin write(' коэффициент системы [',i,',',j,']='); readln(z[i,j]); end; end; end; procedure wwodf; var i:integer; begin writeln('Введите координаты свободного вектора f:'); for i:=1 to p do readln(f[i]); end; procedure wwodl; var i: integer; begin for i:=1 to p do l[i]:=1; end; procedure wwodx; var i:integer; begin writeln('Введите координаты вектора x (начального приближения) :'); for i:=1 to p do readln(x[i]); end; procedure wwodk; var i,j:integer;
132
begin writeln('Ввод показателей степеней:'); for i:=1 to p do begin for j:=1 to p do begin write(' ',i,'-ая строка уравнения, степень при ',j,'-ом неизвестном:'); readln(k1[i,j]); end; end; end; procedure umnog1; var i,j:integer; begin for i:=1 to p do begin for j:=1 to p do begin x1[i,j]:=exp(k1[i,j]*ln(x[j])); end; end; end; procedure umnog; var i,j : integer; begin for i:=1 to p do begin m:=0; for j:=1 to p do begin m1:=z[i,j]*x1[i,j]; m:=m1+m; end; s[i]:=m; end; end; procedure scalf; var i :integer; begin g:=0; for i:=1 to p do begin g1:=f[i]*l[i]; g:=g+g1; end; end; procedure scalx; var i:integer; begin h:=0; for i:=1 to p do begin h1:=x[i]*l[i]; h:=h+h1; end; end;
133
procedure scalAx; var i: integer; begin u:=0; for i:=1 to p do begin u1:=s[i]*l[i]; u:=u1+u; end; end; procedure ttt; var t: real; begin t:=g/(h-u); end; procedure rrr ; var i: integer; begin for i:=1 to p do a[i]:=s[i]*t; end; procedure summ; var i: integer; begin for i:=1 to p do y[i]:=a[i]+f[i]; end; procedure wewod; var i: integer; begin for i:=1 to p do write(y[i]:11:8,' '); end; begin { основная программа } writeln('Решение нелинейного уравнения вида x=F(x)+f, с нелинейным оператором F(x):'); writeln('Введите размерность матрицы:'); readln(p); wwodmatr; wwodf; wwodl; wwodx;wwodk; scalf; writeln('ВВЕДИТЕ КОЛИЧЕСТВО ИТЕРАЦИЙ:'); readln(r); for k:=1 to r do begin umnog1; umnog; scalx; scalAx;
134
t:=g/(h-u); rrr; summ; write(k,':'); wewod; for k2:=1 to p do x[k2]:=y[k2]; writeln; end; writeln('Итак, на ',r,'-м шаге получили приближения'); writeln(' к решению нелинейного уравнения вида x=F(x)+f'); readln; end.
135 §5. Спектральный радиус.
program wert; {uses printer;} var a :array [1..100,1..100] of real; b,d,c,k :array [1..100] of real; maxi,mini,r,c1,p : real; alf, beta :real; i,j,t,l,s : integer; procedure wwod; var i,j:integer; begin writeln('Ввод элементов матрицы А:'); {writeln(lst,'Ввод элементов матрицы А:');} for i:=1 to s do begin for j:=1 to s do begin write('элемент A[',i,',',j,']='); { write(lst,'элемент A[',i,',',j,']='); } readln(a[i,j]); { writeln(lst,a[i,j]:5:3);} end; end; writeln('Введите координаты вектора u (координаты должны'); writeln('быть больше нуля):'); { writeln(lst,'Введите координаты вектора u:');} for i:=1 to s do begin readln(b[i]); { writeln(lst,b[i]:4:4);} end; end; procedure umnog; var r,c1:real; i,j:integer; begin for i:=1 to s do begin r:=0; for j:=1 to s do begin c1:=a[i,j]*k[j]; r:=r+c1; end; c[i]:=r; end; end;
136
procedure delen; var i:integer; begin for i:=1 to s do d[i]:=c[i]/b[i]; end; procedure wibor; var i:integer; begin maxi:=d[1]; for i:=2 to s do begin if d[i]>maxi then maxi:=d[i]; end; mini:=d[1]; for i:=2 to s do begin if d[i]<mini then mini:=d[i]; end; end; begin { основная программа } writeln('Определение спектрального радиуса матрицы А:'); writeln('Введите размерность матрицы:'); readln(s); wwod; for i:=1 to s do k[i]:=b[i]; writeln('Введите количество приближений:'); { writeln(lst,'введите количество приближений:');} readln(t); { writeln(lst,t:4);} for i:=1 to t do begin umnog; delen; wibor; p:=1/i; (alf):=(exp(p*ln(abs(mini)))); (beta):=(exp(p*ln(abs(maxi)))); writeln(i,':', alf:11:8,' ',beta:11:8); { writeln(lst,i,':', alf:11:8,' ',beta:11:8);} for l:=1 to s do k[l]:=c[l]; readln; end; writeln('Итак мы получили на ',t,'-м шаге приближение'); writeln('к спектральному радиусу "снизу"- ',alf:11:8,' и "сверху"- ',beta:11:8,''); readln; end.
137 §6.Собственный вектор.
program qq; var t0,t1,t2,t3,t4,t5,t6,t7,t8,g1,g2,max1,max2,max3,min3:real; k1,k2,k3,k4,k,y,y1,y2,y3,y4,max4,max5,max6:real; i,n,r,i1,j,l,p,w:integer; a,b: array [1..30,1..30] of real; x0,u0,c,c1,c2,c3,c4,c5,c6,x00,u1,v1,x1,z1,z2,x: array [1..30] of real; procedure wwod; var i,j: integer; begin writeln('Введите размерность матрицы А:'); readln(n); writeln('Ввод элементов матрицы А:'); for i:=1 to n do begin for j:=1 to n do begin write('введите элемент матрицы A[ ',i,',',j,']='); readln(a[i,j]); end; end; writeln('Введите координаты начального приближения вектора X:'); for i:=1 to n do readln(x0[i]); writeln('Введите координаты вектора u0:'); for i:=1 to n do readln(u0[i]); end; procedure byfer; begin x00:=x0; x:=x0; end; procedure umn; var i,j:integer; begin for i:=1 to n do begin t0:=0; for j:=1 to n do begin t0:=a[i,j]*x00[j]+t0; end; c[i]:=t0; end; for i:=1 to n do c1[i]:=c[i]/u0[i]; max1:=c1[1]; for i:=2 to n do begin if c1[i]>max1 then max1:=c1[i];
138
end; end; procedure umn2; var i,j : integer; begin for i:=1 to n do begin t2:=0; for j:=1 to n do begin t2:=b[i,j]*x0[j]+t2; end; c5[i]:=t2; end; end; begin {основная программа} wwod; byfer; writeln('Введите количество приближений:'); readln(r); writeln('Соответствующие приближения к координатам собственного вектора:'); for i1:=1 to r do begin umn; { writeln('матрица B:');} for i:=1 to n do c2[i]:=c[i]/(max1); if (i1=1) then begin for i:=1 to n do x1[i]:=c2[i]; end; write(i1,':',' '); for i:=1 to n do write(c2[i]:6:6,' '); for i:=1 to n do x00[i]:=c2[i]; writeln; end; readln; writeln('Получим теперь двустороннее приближение к собственному вектору:'); for i:=1 to n do begin t1:=0; for j:=1 to n do begin t1:=a[i,j]*x0[j]+t1; end; c3[i]:=t1; end; for i:=1 to n do c4[i]:=c3[i]/u0[i]; max2:=c4[1]; for i:=2 to n do begin if c4[i]>max2 then max2:=c4[i]; end; for i:=1 to n do begin
139
for j:=1 to n do begin b[i,j]:=a[i,j]/(max2); {write(b[i,j]:3:3,' ');} end; {writeln;} end; for i:=1 to n do c6[i]:=c3[i]/x0[i]; min3:=c6[1]; for i:=2 to n do begin if c6[i]<min3 then min3:=c6[i]; end; max3:=c6[1]; for i:=2 to n do begin if c6[i]>max3 then max3:=c6[i]; end; { for i:=1 to n do writeln(c6[i]:4:4);} writeln('a=',min3:3:3, 'b=',max3:3:3); writeln('Введите первое наибольшее значение матрицы А:'); readln(k1); writeln('Введите второе наибольшее значение матрицы А:'); readln(k2); writeln('Введите первое наименьшее значение матрицы А:'); readln(k3); writeln('Введите второе наименьшее значение матрицы А:'); readln(k4); k:=sqrt((k1*k2)/(k3*k4)); writeln('постоянная оператора сжатия-',k:3:3); g1:=min3/max3; g2:=max3/min3; t3:=(k-1)/2; t4:=(k-1)/(k+1); readln; for l:=1 to r do begin t5:=exp(l*ln(t4)); t6:=t3*t5; t7:=exp(t6*ln(g1)); t8:=exp(t6*ln(g2)); for i:=1 to n do x00[i]:=x0[i]; umn; for i:=1 to n do begin c5[i]:=c[i]/max1; end; for i:=1 to n do begin u1[i]:=t7*c5[i]; v1[i]:=t8*c5[i]; end; for i:=1 to n do begin write(l,':'); write(u1[i]:5:5,' ',v1[i]:5:5);
140
writeln; end; readln; for i:=1 to n do x0[i]:=c5[i]; writeln; end; readln; writeln('Теперь оценим степень близости к точному решению'); for i:=1 to n do z1[i]:=x1[i]/x0[i]; max4:=z1[1]; for i:=2 to n do begin if z1[i]>max4 then max4:=z1[i]; end; for i:=1 to n do begin z2[i]:=x[i]/x1[i]; { writeln(z2[i]:3:3);} end; max5:=z2[1]; for i:=2 to n do begin if z2[i]>max5 then max5:=z2[i]; end; max6:=max4; if max5>max6 then max6:=max5; y:=ln(max6); y1:=(k-1)/(k+1); writeln('Введите номер приближения с котoрого вы хотите определить расстояние до точного решения:'); readln(w); y2:=exp(w*ln(y1)); y3:=y2/(1-y1); y4:=y3*y; writeln('Вы находитесь от точного решения на расстоянии:',y4:8:8); readln; end.
141 §7.Об одном итерационном методе решения системы линейных алгебраических уравнений вида x = Ax + f с квадратной матрицей A , в случае, когда наибольшее по модулю собственное значение матрицы A , больше чем единица.
program trt; {$N+,E+} type matr= record b:array [1..10,1..10] of extended; x,l2:array [1..10] of extended; G:extended; end; matx= array[1..20] of matr; var u: matx; a1,s,a2,a3,a,a0 :array [1..10,1..10] of extended; y0,l0,y00,l00,f,c,cw,c1,l,y,y1,l1,x,z0,z,x1,c2,c3:array [1..10] of extended; i,j,n,k,k1,r0,r,q,w,v,s1,iq:integer; t,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,G1,t01,t11,t21,t31,h:extended; procedure wwod; var i,j: integer; begin writeln('Введите размерность матрицы А:'); readln(n); writeln('Ввод элементов матрицы А:'); for i:=1 to n do begin for j:=1 to n do begin write('элемент A[',i,',',j,']='); readln(a[i,j]); end; end; writeln('Ввод свободного вектора f:'); for i:=1 to n do begin readln(f[i]); end; end; procedure byfer; var i,j:integer; begin for i:=1 to n do begin for j:=1 to n do begin a0[i,j]:=a[i,j];
142
end; end; end; procedure obr_A; var i,j:integer; begin for i:=1 to n do begin for j:=1 to n do begin a1[i,j]:=a0[j,i]; end; end; writeln('Для отыскания собственных значений необходимо'); writeln('ввести вектора l0 и y0.'); writeln; writeln('Введите вектор l0:'); for i:=1 to n do begin readln(l0[i]); end; writeln('Введите вектор y0:'); for i:=1 to n do begin readln(y0[i]); end; end; procedure byfer2; var i :integer; begin for i:=1 to n do begin y00[i]:=y0[i]; l00[i]:=l0[i]; end; end; Procedure otisk; var i,j : integer; begin for i:=1 to n do begin t:=0; for j:=1 to n do begin t:=a0[i,j]*y00[j]+t; end; c[i]:=t; end; t1:=0; for i:=1 to n do begin t1:=l00[i]*c[i]+t1;
143
end; t2:=0; for i:=1 to n do begin t2:=l00[i]*y00[i]+t2; end; u[q].G:=abs(t1/t2); for i:=1 to n do begin y[i]:=u[q].G*c[i]; end; for i:=1 to n do begin t3:=0; for j:=1 to n do begin t3:=a1[i,j]*l00[j]+t3; end; c1[i]:=t3; end; for i:=1 to n do begin l[i]:=u[q].G*c1[i]; end; end; procedure otisk2; var i,j: integer; begin for i:=1 to n do begin t01:=0; for j:=1 to n do begin t01:=a0[i,j]*y00[j]+t01; end; c[i]:=t01; end; t11:=0; for i:=1 to n do begin t11:=l00[i]*c[i]+t11; end; t21:=0; for i:=1 to n do begin t21:=l00[i]*y00[i]+t21; end; G1:=abs(t11/t21); for i:=1 to n do begin y[i]:=G1*c[i]; end; for i:=1 to n do begin t31:=0;
144
for j:=1 to n do begin t31:=a1[i,j]*l00[j]+t31; end; c1[i]:=t31; end; for i:=1 to n do begin l[i]:=G1*c1[i]; end; end; procedure normma; var i:integer; begin for i:=1 to n do begin y1[i]:=sqr(y[i]); l1[i]:=sqr(l[i]); end; t4:=0; t5:=0; for i:=1 to n do begin t4:=y1[i]+t4; t5:=l1[i]+t5; end; t6:=sqrt(t4); t7:=sqrt(t5); for i:=1 to n do begin u[q].x[i]:=y[i]/t6; u[q].l2[i]:=l[i]/t7; end; end; procedure vivod; var i:integer; begin for i:=1 to n do begin writeln(u[q].x[i]:13:13,' ',u[q].l2[i]:13:13); end; end; procedure sobstv; var i,j:integer; begin obr_A; byfer2; writeln('Введите количество приближений для отыскания'); writeln('собственных векторов l,y операторов А и А~ и'); writeln('собственного значения T оператора А:'); readln(k); for k1:=1 to k do
145
begin otisk; normma; writeln(k1,':',' ', 'T=',u[q].G:13:13); vivod; for i:=1 to n do begin y00[i]:=y[i]; l00[i]:=l[i]; end; end; end; procedure metod2; var i,j: integer; begin for i:=1 to n do begin for j:=1 to n do begin u[q].b[i,j]:=a0[i,j]-u[q].G*u[q].x[i]*u[q].l2[j]; end; end; end; procedure metod1; var i: integer; begin writeln('Введите начальные приближения для отыскания решения'); writeln('уравнения вида y=By+f:'); for i:=1 to n do begin readln(z0[i]); end; end; procedure metod3; var i,j:integer; begin for i:=1 to n do begin t8:=0; for j:=1 to n do begin t8:=u[q].b[i,j]*z0[j]+t8; end; z[i]:=t8+f[i]; end; end; procedure vivod1; var i: integer; begin for i:=1 to n do begin write(z[i]:13:13,' ');
146
end; end; procedure ccc; var i,j: integer; begin for i:=1 to n do begin for j:=1 to n do begin if (i=j) then s[i,j]:=1 else s[i,j]:=0; end; end; for i:=1 to n do begin for j:=1 to n do begin a2[i,j]:=s[i,j]-a[i,j] end; end; for i:=1 to n do begin t9:=0; for j:=1 to n do begin t9:=a2[i,j]*u[1].x[j]+t9; end; c2[i]:=t9; end; for i:=1 to n do begin for j:=1 to n do begin a3[i,j]:=a[i,j]-s[i,j]; end; end; for i:=1 to n do begin t10:=0; for j:=1 to n do begin t10:=a3[i,j]*z[j]+t10; end; c3[i]:=t10+f[i]; end; h:=c3[1]/c2[1]; for i:=1 to n do begin x1[i]:=z[i]+h*u[1].x[i]; end; end; procedure ccc1; var i,j: integer; begin for i:=1 to n do begin
147
for j:=1 to n do begin if (i=j) then s[i,j]:=1 else s[i,j]:=0; end; end; for i:=1 to n do begin for j:=1 to n do begin a2[i,j]:=s[i,j]-u[s1].b[i,j]; end; end; for i:=1 to n do begin t9:=0; for j:=1 to n do begin t9:=a2[i,j]*u[s1+1].x[j]+t9; end; c2[i]:=t9; end; for i:=1 to n do begin for j:=1 to n do begin a3[i,j]:=u[s1].b[i,j]-s[i,j]; end; end; for i:=1 to n do begin t10:=0; for j:=1 to n do begin t10:=a3[i,j]*z[j]+t10; end; c3[i]:=t10+f[i]; end; h:=c3[1]/c2[1]; for i:=1 to n do begin x1[i]:=z[i]+h*u[s1+1].x[i]; end; end; begin {основная программа} wwod; q:=0; byfer; repeat q:=q+1; sobstv; metod2; writeln(q,'-я матрица B:'); for i:=1 to n do begin
148
for j:=1 to n do begin a0[i,j]:=u[q].b[i,j]; a1[i,j]:=a0[j,i]; write( u[q].b[i,j]:4:4,' '); end; writeln; end; byfer2; for w:=1 to 9 do begin otisk2; for iq:=1 to n do begin y00[iq]:=y[iq]; l00[iq]:=l[iq]; end; end; writeln('T=',G1:5); if G1>1 then writeln('На ',q,'-ом шаге спектральный радиус больше единицы.') else v:=1 until v=1; readln; metod1; writeln('Введите количество приближений для отыскания решения уравнения y=By+f:'); readln(r); for r0:=1 to r do begin metod3; write(r0,':'); vivod1; for i:=1 to n do z0[i]:=z[i]; writeln; end; for s1:=(q-1) downto 1 do begin ccc1; z:=x1; end; readln; writeln('Решением исходного уравнения x=Ax+f есть вектор:'); ccc; for i:=1 to n do begin writeln(x1[i]:13:13); end; readln; end.
149 §8. Получение двусторонних оценок точного решения
* x операторного уравнения вида x = Ax + f , в случае, когда спектральный радиус не обязательно меньше единицы.
program wer2; var t1,t2,t3,max1,min1,l,min2,s1,min3,s2,s3,min4,t4:real; n,k1,k2,k3,i,j,i1,k4,i2,i3,i4 :integer; a: array [1..30,1..30] of real; x,f,c,u1,u2,u3,u4,u5,u6,u7,u8,u0,u00,u9,u10,u11,u12,u13,u14,u15,u16,u140,u100: array [1..30] of real; procedure wwodm; var i,j: integer; begin writeln('Введите размерность матрицы А:'); readln(n); for i:=1 to n do begin for j:=1 to n do begin write('введите элемент матрицы A[ ',i,',',j,']='); readln(a[i,j]); end; end; end; procedure wwodv; var i:integer; begin writeln('введите координаты свободного вектора f:'); for i:=1 to n do readln(f[i]); end; procedure wwodx; var i:integer; begin writeln('введите координаты начального приближения Х:'); for i:=1 to n do readln(x[i]); writeln('введите порядок определения для приближений:'); readln(k1); readln(k2); readln(k3); end; procedure umnog; var i,j: integer; begin for i:=1 to n do begin l:=0; for j:=1 to n do begin
150
l:=a[i,j]*x[j]+l; end; c[i]:=l+f[i]; end; end; procedure umnog2; var i,j: integer; begin for i:=1 to n do begin u9[i]:=(max1*(u2[i]-u1[i]))-(u3[i]-u2[i]); end; writeln('Координаты вектора v0:'); for i:=1 to n do begin writeln(u9[i]:6:6); end; for i:=1 to n do begin u13[i]:=(u3[i]-u2[i])-(min1*(u2[i]-u1[i])); end; writeln('Координаты вектора w0:'); for i:=1 to n do begin writeln(u13[i]:6:6); end; end; begin {основная программа} wwodm; wwodv; wwodx; for i1:=1 to k3 do begin umnog; if (i1=k1) then begin for i:=1 to n do u1[i]:=c[i]; end; if (i1=k2) then begin for i:=1 to n do u2[i]:=c[i]; end; if (i1=k3) then begin for i:=1 to n do u3[i]:=c[i]; end; for i:=1 to n do x[i]:=c[i]; end; writeln('искомый вектор u[',k1,']:'); for i:=1 to n do writeln(u1[i]:7:7); readln; writeln('искомый вектор u[',k2,']:');
151
for i:=1 to n do writeln(u2[i]:7:7); readln; writeln('искомый вектор u[',k3,']:'); for i:=1 to n do writeln(u3[i]:7:7); readln; for i:=1 to n do begin u4[i]:=(u3[i]-u2[i])/(u2[i]-u1[i]); end; max1:=u4[1]; for i:=2 to n do begin if u4[i]>max1 then max1:=u4[i]; end; writeln('"гамма" равно - ',max1:5:5); min1:=u4[1]; for i:=2 to n do begin if u4[i]<min1 then min1:=u4[i]; end; writeln('"бетта" равно - ',min1:5:5); t1:=(max1)/(1-max1); t2:=(min1)/(1-min1); for i:=1 to n do begin u5[i]:=u3[i]+t1*(u3[i]-u2[i]); u6[i]:=u3[i]+t2*(u3[i]-u2[i]); end; writeln('точное решение заключено между следующими векторами:'); for i:=1 to n do begin writeln( ' ',u6[i]:5:5,' ',u5[i]:5:5); end; readln; writeln('Теперь произведем улучшение полученных оценок.'); readln; writeln('Введите координаты вектора u0:'); for i:=1 to n do begin readln(u0[i]); u00[i]:=u0[i]; end; k4:=k2-k1; for i2:=1 to k4 do begin for i:=1 to n do begin s1:=0; for j:=1 to n do begin s1:=a[i,j]*u00[j]+s1; end; u7[i]:=s1; end; for i3:=1 to n do u00[i3]:=u7[i3];
152
end; for i:=1 to n do u8[i]:=u7[i]/u0[i]; min2:=u8[1]; for i:=2 to n do begin if u8[i]<min2 then min2:=u8[i]; end; writeln('q0=',min2:3:3); readln; umnog2; readln; for i3:=1 to k4 do begin for i:=1 to n do begin s2:=0; for j:=1 to n do begin s2:=a[i,j]*u9[j]+s2; end; u10[i]:=s2; end; for i:=1 to n do u9[i]:=u10[i]; end; for i:=1 to n do u100[i]:=u10[i]/u0[i]; min3:=u100[1]; for i:=2 to n do begin if u100[i]<min3 then min3:=u100[i]; end; writeln('q=',min3:5:5); t3:=(min3)/((1-max1)*(1-min2)); for i:=1 to n do u11[i]:=t3*u0[i]; for i:=1 to n do begin u12[i]:=u5[i]-u11[i]; end; for i4:=1 to k4 do begin for i:=1 to n do begin s3:=0; for j:=1 to n do begin s3:=a[i,j]*u13[j]+s3; end; u14[i]:=s3; end; for i:=1 to n do u13[i]:=u14[i]; end; for i:=1 to n do u140[i]:=u14[i]/u0[i]; min4:=u140[1]; for i:=2 to n do begin if u140[i]<min4 then min4:=u140[i];
153
end; writeln('q1=',min4:6:6); t4:=(min4)/((1-min1)*(1-min2)); for i:=1 to n do u15[i]:=t4*u0[i]; for i:=1 to n do begin u16[i]:=u6[i]+u15[i]; end; writeln('После улучшения оценок получаем следующие векторы:'); for i:=1 to n do begin writeln(u16[i]:6:6,' ',u12[i]:6:6); end; readln; end.
154 §9. О некоторых подходах к уточнению границ решения операторных уравнений вида x = Ax + f в случае, когда спектральный радиус r( ) A не обязательно меньше единицы.
program wert; type Mat = Array[1..30,1..30] of real; Vec = Array[1..30] of real; var a : Mat; f,l,x,s,y,b,u1,u2,u3,u4,u5,u6,u0,u00,u7,u8,u9,u10,u11,u12 :Vec; u13,u14,u15,u16,u100,u140:Vec; m,m1,g,h,h1,t,t1,t2,max1,min1,s1,min2,min3,min4,s2,s3,t3,t4:real; r,i,j,k,p,k1,k2,k3,i1,k4,n,i2,i3,i4 : integer; procedure wwodmatr; var i,j:integer; begin for i:=1 to p do begin for j:=1 to p do begin write('Введите элемент матрицы А[',i,',',j,']='); readln(a[i,j]); end; end; end; procedure wwodf; var i:integer; begin writeln('Введите координаты свободного вектора f:'); for i:=1 to p do readln(f[i]); end; procedure wwodl; var i: integer; begin for i:=1 to p do l[i]:=1; end; procedure wwodx; var i:integer; begin writeln('Введите координаты вектора x (начального приближения) :'); for i:=1 to p do readln(x[i]); writeln('введите порядок определения для приближений:'); readln(k1); readln(k2); readln(k3);
155
end; procedure umnog; var i,j : integer; begin for i:=1 to p do begin m:=0; for j:=1 to p do begin m:=a[i,j]*x[j]+m; end; s[i]:=m; end; end; procedure scalf; var i :integer; begin g:=0; for i:=1 to p do begin g:=f[i]*l[i]+g; end; end; procedure scalx; var i:integer; begin h:=0; for i:=1 to p do begin h:=x[i]*l[i]+h; end; end; procedure scalAx; var i: integer; begin h1:=0; for i:=1 to p do begin h1:=s[i]*l[i]+h1; end; end; procedure ttt; begin t:=g/(h-h1); end; procedure rrr ; var i: integer; begin for i:=1 to p do b[i]:=s[i]*t; end;
156
procedure summ; var i: integer; begin for i:=1 to p do y[i]:=b[i]+f[i]; end; procedure umnog2; var i,j: integer; begin for i:=1 to p do begin u9[i]:=(max1*(u2[i]-u1[i]))-(u3[i]-u2[i]); end; writeln('Координаты вектора v0:'); for i:=1 to p do begin writeln(u9[i]:6:6); end; for i:=1 to p do begin u13[i]:=(u3[i]-u2[i])-(min1*(u2[i]-u1[i])); end; writeln('Координаты вектора w0:'); for i:=1 to p do begin writeln(u13[i]:6:6); end; end; begin { основная программа } writeln('Введите размерность матрицы А:'); readln(p); wwodmatr; wwodf; wwodl; wwodx; scalf; for i1:=1 to k3 do begin umnog; scalx; scalAx; ttt; rrr; summ; if (i1=k1) then begin for i:=1 to p do u1[i]:=y[i]; end; if (i1=k2) then begin for i:=1 to p do u2[i]:=y[i]; end; if (i1=k3) then begin for i:=1 to p do u3[i]:=y[i]; end; for i:=1 to p do begin
157
x[i]:=y[i]; end; end; writeln('искомый вектор u[',k1,']:'); for i:=1 to p do writeln(u1[i]:7:7); readln; writeln('искомый вектор u[',k2,']:'); for i:=1 to p do writeln(u2[i]:7:7); readln; writeln('искомый вектор u[',k3,']:'); for i:=1 to p do writeln(u3[i]:7:7); readln; for i:=1 to p do begin u4[i]:=(u3[i]-u2[i])/(u2[i]-u1[i]); end; max1:=u4[1]; for i:=2 to p do begin if u4[i]>max1 then max1:=u4[i]; end; writeln('"гамма" равно - ',max1:5:5); min1:=u4[1]; for i:=2 to p do begin if u4[i]<min1 then min1:=u4[i]; end; writeln('"бетта" равно - ',min1:5:5); t1:=(max1)/(1-max1); t2:=(min1)/(1-min1); for i:=1 to p do begin u5[i]:=u3[i]+t1*(u3[i]-u2[i]); u6[i]:=u3[i]+t2*(u3[i]-u2[i]); end; writeln('точное решение заключено между следующими векторами:'); for i:=1 to p do begin writeln( ' ',u6[i]:15:15,' ',u5[i]:15:15); end; readln; writeln('Теперь произведем улучшение полученных оценок.'); readln; n:=p; writeln('Введите координаты вектора u0:'); for i:=1 to n do begin readln(u0[i]); u00[i]:=u0[i]; end; k4:=k2-k1; for i2:=1 to k4 do begin
158
for i:=1 to n do begin s1:=0; for j:=1 to n do begin s1:=a[i,j]*u00[j]+s1; end; u7[i]:=s1; end; for i3:=1 to n do u00[i3]:=u7[i3]; end; for i:=1 to n do u8[i]:=u7[i]/u0[i]; min2:=u8[1]; for i:=2 to n do begin if u8[i]<min2 then min2:=u8[i]; end; writeln('q0=',min2:3:3); readln; umnog2; readln; for i3:=1 to k4 do begin for i:=1 to n do begin s2:=0; for j:=1 to n do begin s2:=a[i,j]*u9[j]+s2; end; u10[i]:=s2; end; for i:=1 to n do u9[i]:=u10[i]; end; for i:=1 to n do u100[i]:=u10[i]/u0[i]; min3:=u100[1]; for i:=2 to n do begin if u100[i]<min3 then min3:=u100[i]; end; writeln('q=',min3:5:5); t3:=(min3)/((1-max1)*(1-min2)); for i:=1 to n do u11[i]:=t3*u0[i]; for i:=1 to n do begin u12[i]:=u5[i]-u11[i]; end; for i4:=1 to k4 do begin for i:=1 to n do begin s3:=0; for j:=1 to n do begin s3:=a[i,j]*u13[j]+s3; end;
159
u14[i]:=s3; end; for i:=1 to n do u13[i]:=u14[i]; end; for i:=1 to n do u140[i]:=u14[i]/u0[i]; min4:=u140[1]; for i:=2 to n do begin if u140[i]<min4 then min4:=u140[i]; end; writeln('q1=',min4:6:6); t4:=(min4)/((1-min1)*(1-min2)); for i:=1 to n do u15[i]:=t4*u0[i]; for i:=1 to n do begin u16[i]:=u6[i]+u15[i]; end; writeln('После улучшения оценок получаем следующие векторы:'); for i:=1 to n do begin writeln(u16[i]:6:9,' ',u12[i]:6:9); end; readln; end. end.
160 §10. “Гибрид” методов ускорения сходимости монотонных приближений к решению * x уравнения вида x = Ax + f и однопараметрического итеративного агрегирования.
program wert; { uses printer;} var lr,ch,ch1,zn,zn1,f,sn,sn1,sn2,sn3,z0,z01,z1,a1,a2,a00,b00,b0,u0,v0,u,v,p,q,p1,q1,u 1,v1: array[1..25] of real; a: array[1..25,1..25] of real; it,it1,h1,h2,h3,h11,h12,s,k,b,kt,k1,d0,d1,d01,d10,m01,m02,d02,d12,d012,d102,k0: real; g,g2,t,t1,t2,t3,r,r1,r2,r3,r4,r5,r6,r7,r8,r9,r10,r11:real; c,n1,i,j,n,x,hl,i1,l :integer; procedure wwod; var i,j:integer; begin writeln('введите размерность матрицы A:'); readln(n); writeln('Ввод элементов матрицы А:'); for i:=1 to n do begin for j:=1 to n do begin write('элемент A[',i,',',j,']='); readln(a[i,j]); end; end; writeln('Введите координаты свободного вектора f:'); for i:=1 to n do begin readln(f[i]); end; { writeln('Введите координаты вектора z0 :'); for i:=1 to n do begin readln(z0[i]); end; } for i:=1 to n do lr[i]:=1; end; procedure byferr; var i,j:integer; begin for i:=1 to n do begin z01[i]:=z0[i]; { writeln(u01[i]:4:4)} end; end; procedure umn; var i,j: integer; s: real;
161
begin for i:=1 to n do begin s:=0; for j:=1 to n do begin s:=a[i,j]*z01[j]+s; end; a1[i]:=s; end; end; procedure it_agr; var i,j:integer; begin for i:=1 to n do begin r:=0; r1:=0; for j:=1 to n do begin r:=a[i,j]*u0[j]+r; r1:=a[i,j]*v0[j]+r1; end; sn[i]:=r; sn1[i]:=r1; end; r2:=0; r3:=0; for i:=1 to n do begin r2:=sn[i]*lr[i]+r2; r3:=sn1[i]*lr[i]+r3; end; r4:=0; r5:=0; for i:=1 to n do begin r4:=u0[i]*lr[i]+r4; r5:=v0[i]*lr[i]+r5; end; g:=0; for i:=1 to n do begin g:=f[i]*lr[i]+g; end; t:=g/(r4-r2); t1:=g/(r5-r3); for i:=1 to n do begin u[i]:=t*sn[i]+f[i]; v[i]:=(t1)*sn1[i]+f[i]; end; end; procedure otn; var i,j:integer; begin
162
for i:=1 to n do begin zn[i]:=v0[i]-v[i]; ch[i]:=u[i]-u0[i]; end; for i:=1 to n do begin p[i]:=ch[i]/zn[i]; end; h2:=0; for i:=1 to n do begin h2:=p[i]+h2; end; m01:=h2/n; for i:=1 to n do begin q[i]:=zn[i]/ch[i]; end; h3:=0; for i:=1 to n do begin h3:=q[i]+h3; end; m02:=h3/n; end; begin { начало основной программы } wwod; byferr; writeln('Введите вектор u0:'); for i:=1 to n do begin readln(u0[i]); end; writeln('Введите вектор v0:'); for i:=1 to n do begin readln(v0[i]); end; writeln('Введите количество приближений:'); readln(x); for l:=1 to x do begin it_agr; otn; for i:=1 to n do begin if (m01=-1) or (m02=-1) then begin u1[i]:=u[i]; v1[i]:=v[i]; writeln(l,':',u1[i]:11:8,' ',v1[i]:11:8); writeln('деление на ноль'); end else begin u1[i]:=(u[i]+m01*v[i])/(1+m01); v1[i]:=(v[i]+m02*u[i])/(1+m02); writeln(l,':',u1[i]:11:8,' ',v1[i]:11:8); { writeln(lst,l,':',u1:11:8,' ',v1:11:8);} end; end;
163
for i1:=1 to n do begin u0[i1]:=u[i1]; v0[i1]:=v[i1]; end; readln; end; end.
program wert; { uses printer;} var lr,ch,ch1,zn,zn1,f,sn,sn1,sn2,sn3,z0,z01,z1,a1,a2,a00,b00,b0,u0,v0,u,v,p,q,p1,q1,u 2,v2,u02,c72: array[1..25] of real; a: array[1..25,1..25] of real; it,it1,h1,h2,h3,h11,h12,s,k,b,kt,k1,d0,d1,d01,d10,m01,m02,d02,d12,d012,d102,m0 12,m022,u1,v1,k0:real; g,g2,t,t1,t2,t3,r,r1,r2,r3,r4,r5,r6,r7,r8,r9,r10,r11,h9,h10,h88,h99:real; c,n1,i,j,n,x,hl,i1,l,dd :integer; procedure wwod; var i,j:integer; begin writeln('введите размерность матрицы A:'); readln(n); writeln('Ввод элементов матрицы А:'); for i:=1 to n do begin for j:=1 to n do begin write('элемент A[',i,',',j,']='); readln(a[i,j]); end; end; writeln('Введите координаты свободного вектора f:'); for i:=1 to n do begin readln(f[i]); end; writeln('Введите координаты вектора z0 :'); for i:=1 to n do begin readln(z0[i]); end; for i:=1 to n do lr[i]:=1; end; procedure byferr; var i,j:integer; begin for i:=1 to n do begin z01[i]:=z0[i]; { writeln(u01[i]:4:4)} end;
164
end; procedure umn; var i,j: integer; s: real; begin for i:=1 to n do begin s:=0; for j:=1 to n do begin s:=a[i,j]*z01[j]+s; end; a1[i]:=s; end; end; procedure it_agr; var i,j:integer; begin for i:=1 to n do begin r:=0; r1:=0; for j:=1 to n do begin r:=a[i,j]*u0[j]+r; r1:=a[i,j]*v0[j]+r1; end; sn[i]:=r; sn1[i]:=r1; end; r2:=0; r3:=0; for i:=1 to n do begin r2:=sn[i]*lr[i]+r2; r3:=sn1[i]*lr[i]+r3; end; r4:=0; r5:=0; for i:=1 to n do begin r4:=u0[i]*lr[i]+r4; r5:=v0[i]*lr[i]+r5; end; g:=0; for i:=1 to n do begin g:=f[i]*lr[i]+g; end; t:=g/(r4-r2); t1:=g/(r5-r3); for i:=1 to n do begin u[i]:=t*sn[i]+f[i]; v[i]:=(t1)*sn1[i]+f[i]; writeln(v[i]:3:3); end;
165
end; procedure otn; var i,j:integer; begin for i:=1 to n do begin zn[i]:=v0[i]-v[i]; ch[i]:=u[i]-u0[i]; end; h2:=ch[1]; for i:=2 to n do begin if ch[i]<h2 then h2:=ch[i]; end; h9:=zn[1]; for i:=2 to n do begin if zn[i]>h9 then h9:=zn[i]; end; m01:=h2/h9; h3:=zn[1]; for i:=2 to n do begin if zn[i]<h3 then h3:=zn[i]; end; h10:=ch[1]; for i:=2 to n do begin if ch[i]>h10 then h10:=ch[i]; end; m02:=h3/h10; end; procedure byferr2; var i,j : integer; begin for i:=1 to n do begin u2[i]:=u[i]; v2[i]:=v[i]; u02[i]:=u0[i]; c72[i]:=v0[i]; end; end; procedure it_agr2; var i,j:integer; begin for i:=1 to n do begin r6:=0; r7:=0; for j:=1 to n do begin r6:=a[i,j]*u02[j]+r6; r7:=a[i,j]*c72[j]+r7; end;
166
sn2[i]:=r6; sn3[i]:=r7; end; r8:=0; r9:=0; for i:=1 to n do begin r8:=sn2[i]*lr[i]+r8; r9:=sn3[i]*lr[i]+r9; end; r10:=0; r11:=0; for i:=1 to n do begin r10:=u02[i]*lr[i]+r10; r11:=c72[i]*lr[i]+r11; end; g2:=0; for i:=1 to n do begin g2:=f[i]*lr[i]+g2; end; t2:=(g2)/(r10-r8); t3:=(g2)/(r11-r9); for i:=1 to n do begin u2[i]:=(t2)*sn2[i]+f[i]; v2[i]:=(t3)*sn3[i]+f[i]; end; end; procedure otn2; var i,j: integer; begin for i:=1 to n do begin ch1[i]:=(u2[i]-u02[i]); zn1[i]:=(c72[i]-v2[i]); end; h11:=ch1[1]; for i:=2 to n do begin if ch1[i]<h11 then h11:=ch1[i]; end; h88:=zn1[1]; for i:=2 to n do begin if zn1[i]>h88 then h88:=zn[i]; end; m012:=h11/h88; h12:=zn1[1]; for i:=2 to n do begin if zn1[i]<h12 then h12:=zn1[i]; end; h99:=ch1[1]; for i:=2 to n do begin
167
if ch1[i]>h99 then h99:=ch1[i]; end; m022:=h12/h99; end; begin { начало основной программы } wwod; byferr; writeln('Введите вектор u0:'); for i:=1 to n do begin readln(u0[i]); end; writeln('Введите вектор v0:'); for i:=1 to n do begin readln(v0[i]); end; it_agr; otn; writeln('Введите количество приближений:'); readln(x); for i:=1 to n do begin writeln('приближение к ',i,'-ой координате вектора решения:'); byferr2; m012:=m01; m022:=m02; for l:=1 to x do begin if (m012=-1) or (m022=-1) then begin u1:=u2[i]; v1:=v2[i]; writeln(l,':',u1:11:8,' ',v1:11:8); writeln('деление на ноль'); end else begin u1:=(u2[i]+m012*v2[i])/(1+m012); v1:=(v2[i]+m022*u2[i])/(1+m022); writeln(l,':',u1:11:8,' ',v1:11:8); end; for dd:=1 to 4 do begin for i1:=1 to n do begin u02[i1]:=u2[i1]; c72[i1]:=v2[i1]; end; it_agr2; end; otn2; readln; end; end; end.
А также другие работы, которые могут Вас заинтересовать
Мета навчально методичної збірки, яка поєднує всі аутентичні та вітчизняні навчально методичні ресурси, що задовольняють викладання німецької мови у групах нормативного навчання, – допомогти студентам раціонально розподілити й засвоїти програмний навчальний матеріал, правильно організувати самостійну роботу...
Хозяйственное право субъекты и основные положения по предпринимательской деятельности. Предметом хозяйственного права являются общественные отношения в сфере предпринимательской деятельности и связанные с ними не коммерческие отношения включая отношения по государственному регулированию экономики.
Согласившись с одними утверждениями, мы вынуждены принять и те, что из них следуют, независимо от того, нравятся они нам или нет, способствуют нашим целям или, напротив, препятствуют им. Допустив одно, мы тем самым автоматически лишаем себя возможности утверждать другое, несовместимое с уже допущенным.
Подчеркивалось что врач должен уметь спокойно выслушивать больного быть на протяжении всего приема внимательным сердечным дружелюбным способствовать быстрейшему излечению больного и предупреждению рецидивов болезни. Вторые занимались устранением причин болезни.
Несмотря на то что страна перешла к рыночным отношениям до настоящего времени не выработан механизм оценки таких важных объектов анализа как оценка конкурентоспособности продукции условия цен на рынке изучение маркетинговой стратегии предприятия и т.
Технологии аэрокосмического приборостроения а также могут быть использованы студентами инженерных специальностей для совершенствования технологической подготовки в части проведения испытаний аппаратуры различного назначения....
В общем виде рынок и рыночная экономика это система экономических отношений между людьми охватывающая прежде всего процесс производства товаров и услуг по рыночным законам а также процессы распределения обмена и потребления по законам рынка основными из которых являются закон стоимости закон...
Бетон конструкции мостов подбирают в зависимости от требуемых условий прочности морозостойкости и в некоторых случаях водостойкости и водонепроницаемости. В зависимости от вида конструкции их армирования и условий работы класс бетона принимают в соответствии с требованиями приведенными в СНиП.
В практике наладочных работ приходится измерять сопротивления от десятков микроом переходные сопротивления контактов до тысяч мегом сопротивление изоляции. При этом взаимная индуктивность равна Наладка защитно-коммутационной аппаратуры Измерение сопротивления изоляции ЭО и...