Некоторые вопросы решения интервальных систем линейных алгебраических уравнений тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ С,'/! УНИВЕРСИТЕТ

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

ЛЯШКО Марина Александровна

НЕКОТОРЫЕ ВОПРОСЫ РЕШЕНИЯ ИНТЕРВАЛЬНЫХ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

01.01.07 — вычислительная математика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

САНКТ-ПЕТЕРБУРГ 1998

Работа выполнена на кафедре математической физики и вычислительной математики Саратовского государственного университета имени Н.Г.Чернышевского.

Научный руководитель: кандидат физико-математических

наук, доцент

ЗЮЗИН Владимир Сергеевич

Официальные оппоненты: доктор технических наук,

Заслуженный деятель науки и техники РФ, профессор МЕНЬШИКОВ Григорий Григорьевич,

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

НЕСТЕРОВ Вячеслав Михайлович

Ведущая организация: Институт Проблем Точной

Механики и Управления РАН

Защита диссертации состоится "<£9 " &/>/>£/10 1998 г. в " " часов на заседании диссертационного совета К 063.57.16 по защитам диссертаций на соискание ученой степени кандидата физико-метематических наук в Санкт-Петербургском государственном университете по адресу: 199004, Санкт-Петербург, 10-я линия В.О., д.ЗЗ, ауд.88.

С диссертацией можно ознакомиться в научной библиотеке им.М.Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская набережная, 7/9.

Автореферат разослан " 1998 г.

Ученый секретарь

диссертационного совета К 063.57.16 В.Ф.Горьковой

Общая характеристика работы

Актуальность темы. Интервальные системы линейных алгебраических уравнений (ИСЛАУ) возникают как обобщение линейных систем, параметры которых могут принимать значения из заданных интервалов. Известные методы решения линейных систем переносятся на интервальный случай, приобретая ряд специфических особенностей. Теория методов решения ИСЛАУ находится1 в стадии интенсивной разработки. Для оценки скорости сходимости итерационных интервальных методов используется понятие асимптотического фактора сходимости как обобщение понятия множителя в вещественном случае, но до последнего времени для систем общего вида были определены лишь верхние оценки этого значения простейших итерационных методов.

Точное нахождение объединенного множества решений (ОМР) ИСЛАУ, имеющего сложную структуру, требует больших вычислительных затрат, но это множество довольно легко может быть ограничено, например, с помощью какого-либо итерационного метода. Неподвижная точка сжимающего интервального отображения не всегда совпадает с минимальным по ширине интервальным вектором, содержащим ОМР. Поэтому актуальной становится задача определения условий такого совпадения.

Цель исследования. Диссертация посвящена определению скорости сходимости итерационных методов решения интервальной СЛАУ и определению условий совпадения интервальной оболочки объединенного множества решений интервальной СЛАУ и неподвижной точки интервального отображения.

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

Для интервальной СЛАУ со знакопостоянными коэффициентами получены необходимые и достаточные условия совпадения интервальной оболочки объединенного множества решений этой системы с неподвижной точкой соответствующего интервального отображе-

ния. Доказательство проведено двумя способами, один из которых использует развиваемый в диссертации подход перенесения итерационного процесса из пространства IIR" в хорошо изученное пространство Ш,2".

Апробация работы. Результаты диссертации докладывались на Межвузовской конференции молодых ученых "Развитие фундаментальных и прикладных исследований" (Ленинград, 1985 год), на Всесоюзном совещании по интервальной математике (ВЦ СО АН СССР, Красноярск, 1987 год), в Ленинградском отделении математического института им. В. А. Стеклова на семинаре Ю.В. Ма-тиясевича (1987 год), на коференции "Актуальные проблемы прикладной математики" (Саратов, 1991 год), на Межреспубликанском совещании по интервальной математике (Новосибирск, 1996 год).

Структура и объем работы. Структурно работа состоит из введения, указателя основных обозначений, двух глав, списка литературы из 68 наименований и приложения. Объем диссертации — 161 страница, 22 страницы из них — приложение.

Публикации. По теме диссертации опубликовано 10 работ [1]-[10].

Краткое содержание работы

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

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

IIR - множество вещественных интервалов;

х,х - левый и правый конец интервала х соответственно, так что х := [х,х], х,х е Н, х < х;

int(x) := {х 6 Ш.|х < х < х} - внутренность интервала х; IR" - множество n-мерных вещественных векторов;

1Ш" - множество п-мерных интервальных векторов; Щ,тхп _ МН0жес1В0 вещественных тхп-матриц; щтхп _ множество интервальных тхп-матриц; ¡х| := тах {|х|, |х|} - модуль интервала х;

|А| - вещественная тхп-матрица, составленная из модулей интервальных элементов матрицы А;

д(х,у) :=тах{|х—у|,|х—у|} - расстояние между интервалами х и у; если х, у £ 111", то под записью q(x, у) подразумевается п-мерный вещественный вектор, компонентами которого являются расстояния между соответствующими интервальными компонентами векторов х и у;

р(А) - спектральный радиус вещественной квадратной матрицы А.

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

§1.1 содержит основные известные факты и результаты. Одношаговые стационарные методы на множестве Ж" интервальных векторов можно представить в виде итерационной процедуры

Х(*+Ч =/(*(*)), ¿ = 0,1,.... (1)

Скорость сходимости последовательности к х* = 1шц_юо х'^

оценивается с помощью асимптотического фактора сходимости.

Определение1. Пусть х* = /(х*) и пусть 0 - множество всех последовательностей вычисленных по формуле (1) и удовлетворяющих условию Нт^ооХ^ = х*. Тогда величина

а = 8иР{Ит8иР||д(х«,х*)||]^|{х«}Г=0 €

к—юо

1 Алсфельд Г., Херцбергер Ю. Введение в интервальные вычисления,- М.: Мир, 1987.

называется асимптотическим фактором сходимости итераций (1) ж точке х*.

Здесь || ■ || - некоторая норма в IRn, и а не зависит от выбранной нормы.

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

х — Ах + b, A6irx", beint" (2)

задается формулой

.:х(*+1) =Ax(fc)+b, ¿ = 0,1,.... (3)

Асимптотический фактор сходимости этого метода обозначается ат и оценивается сверху следующим образом:

ат < Р(|А|). (4)

Для сходимости метода (3) для любого начального приближения х^ 6 IR" необходимо и достаточно, чтобы р(|А|) < 1. При этом х* = limbec, х^ удовлетворяет уравнению

х* = Ах* + ь. (5)

Чтобы доказать равенство в оценке (4), предлагалось найти начальное приближение , для которого имеет место

limsup HgCxW,**)!!1^ = р(|А|).

к—* оо

Но, как показали дальнейшие исследования, равенство в оценке (4) выполняется не всегда. В частности, Г. Майер2'3 привел и доказал

2Mayer G. On the speed of convergence of the total step method in interval computations. In: Ortiz E.L. (ed) "Numerical Approximation of Partial Differential Equations", North Holland, Amsterdam, 1987.

3Mayer G. On the asymptotic convergence factor of the total step method in interval computation. Lin. Alg. Appl. 85 (1987) 153-164.

необходимые и достаточные условия выполнения строгого неравенства ат < р(|А|) для А с неотрицательными коэффициентами (т.е. с IUj > 0, i,j — 1,п) и неразложимой матрицей |А|.

В §1.2 предложен подход к нахождению точного значения ат, основанный на изучении итерационного процесса в достаточно малой окрестности решения х% который может быть распространен на другие интервальные итерационные методы, что и продемонстрировано в дальнейшем в §1.8 на примере метода Гаусса-Зейделя (короткошагового метода) ив §1.9 на примере метода релаксации для короткошагового случая. Данный подход позволяет проводить сравнение факторов сходимости различных методов.

Пусть а,х 6 ГО,. В случае, когда min (ах, ах,ах, ах) — ах и max (ах, ах, ах, ах) = ах достигаются лишь для одного из четырех зпачений ах,ах,ах,ах, или в случае, когда только один из концов интервала а равен нулю и ни один из концов интервала х не равен нулю, или в случае, когда оба конца интервала а равны нулю, произведение интервалов ах можно представить однозначно в виде:

(au (6)

\ аху \ Я21 а22 J \x j Элементы 2х2-матрицы а^ £ {0, а, ä}, i,j = 1,2, причем один из элеметов каждой строки обязательно равен нулю.

Обозначим через W{A) множество векторов х € ГО", таких что произведения элементов матрицы А= (ау)".=1 из системы (2)

и компонент вектора х= однозначно представляются в виде

(6) при i,j = 1,п. Далее, пусть в уравнении (5) х* £ W(A). От интервальной га-матрицы А и интервальных re-векторов Ь и х* с помощью отображения

er: HR" —► Ш,2", Ж=а(х)-(х1,х1,х2,х2,...,хп,х„)т (7)

можно перейти к точечным 2пх2п-матрице А(х*) и 2п-векторам Ь=ст(Ь) и х*=а(х*). Коэффициенты ay, i,j — 1,2п, матрицы Л(х*) определяются с помощью равенства

а(Ах*)=А(х.*)-а(х*). (8)

Поэтому А(х*) удовлетворяет соотношению Х*—А(Х.*)'Х* + b (что по существу является другой записью равенства (5)).

Заметим, что при отображении а компоненты х* и Ъ, стоящие на т-ом и к-ом месте (1<пг<2п, 1<к<2п), можно менять местами, что влечет за собой перестановку рядов га и к матрицы А(х*). Множество всех 2гсх2п-матриц, образованных из А(х*) перестановками рядов, обозначим А.

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

Х= <г(х) = (X!, х2,.. • , х„, X!, х2,..., х„)т, (9)

и соответствующая 2тгх2п-матрица А(х*) € А будет иметь вид:

где Аа2, А21, А22 6 1ГХП, Аи,А22 - неотрицательные, а Аи, А21 - неположительные матрицы.

Утверждение 1.2.1 Если в сходящемся полношаговом методе (3) х* £ IV(А), то для любой матрицы А(х*) £ А

аТ =. р(А(х*)).

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

Обозначим через В{А) множество всех матриц из ГО,"*" таких, что не менее к = г'+"™°'12 произвольных столбцов в них составлены из наиболее удаленных от нуля концов интервалов a¿j, а остальные столбцы - из ближайших к нулю концов а,-; матрицы А. Ясно, что таких матриц в В(А) будет С* + + ... + СЦ.

Теорема 1.3.1 Пусть матрица А в сходящемся полношаговом методе (3) такова, что а^- > 0, г,= 1 ,п, их* 6 Т7(А). Тогда ат = р{В) для некоторой В £ В{А).

Обозначим теперь через В(А) множество всех матриц из К"*" таких, что ровно к = "+"^"><j2 произвольных столбцов в них составлены из наиболее удаленных от нуля концов интервалов а у, а остальные столбцы - из ближайших к нулю концов ау матрицы А. Ясно, что таких матриц в В(А) будет С*.

Следствие 1.3.1 ат > min

Теорема 1.3.2 Пусть матрица А в сходящемся полношаговом методе (3) такова, что Жу < 0, г, j — 1, п, вх*£ W(A). Тогда ocf = x/XAiÄ^) для некоторых Ai, А2 € ß(A).

Следствие 1.3.2

> G В(А), А < 0,х* е

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

Теорема 1.4.1 Если в сходящемся полношаговом методе (3) X* G W(А), то

<*т > P(F),

где F G 1ГХ", Д- = mm{|ay|, |äy|}, i,j = TJi.

В §1.5 доказываются легко вычисляемые оценки снизу ат для знакопостоянных матриц А в методе (3): для неотрицательных матриц выполняется оценка

a-r > max а,-,- - max la.,1, - 1 <i<n 1<1<П 1 1

а для неположительных — оценки

ат > тах ■ а„- и ат > Ч/^ • а1|П • а2 ^ ■ а2>„_1 •... • а„д • а„д.

1<1<п V

В §1.6 разными способами доказываются условия, достаточные для достижения ат максимально возможного значения.

Теорема 1.6.1 Пусть в сходящемся полношаговом методе (3)

1. матрица А такова, что 0 $ цй(а,-;-), . = 1,п;

2. решение х* уравнения (5) таково, что 0 6 т(;(х*), г = 1,п. Тогда аТ = р(\А\).

Следствие 1.6.1 Если выполнено условие 1 теоремы 1.6.1 и вектор Ь в (2) такой, что 0 £ ш^Ь^), г = 1,71, то ат = р{\А|).

В работе последний результат доказывается с помощью утверждения 1.2.1, а при более слабых требованиях 0 £ х*,г = 1 ,п, или, соответственно, 0 £ Ь,-, г = 1, п, по-другому, с помощью выбора специального начального приближения: х|-0' = [х* — + х^] , г = 1,тг, где А:=/э(|А|), и вектор с положительными координатами хЛ = соответствует собственному числу Л. В § 1.7 дриводится методика определения для некоторого достаточно широкого класса систем эффективной нижней оценки с*г, которая почти всегда является точной, только с использованием информации об А и Ь. Здесь описывается легко алгоритмизируемый способ построения некоторых множеств и х 6 И^А)

(которые существуют не для всех систем).

Теорема 1.7.1 Пусть в системе (2) вектор Ь £ IV(А). Если П(Ь) существует, то аТ > />(Л(Ь)). Если к тому же х* £ И^(А), то аТ = р(Л(Ь)).

Заметим, что х* £ почти всегда, а если Ь € И^А) и П(Ь)

существует, то х* = с(х*) может быть найдено как алгебраическое решение точечной системы х = Л(Ь)х 4- <7(Ь).

В §1.8 приводятся результаты, аналогичные полученным выше, для метода Гаусса-Зейделя, определяемого формулами

х(<:+1) = Ьх(*+1) + (Б + и)х(ь> + Ъ, к = 0,1,..., (10)

где А = Ь + Ю + и, Ъ - строго нижняя треугольная матрица, Ю -диагональная матрица, и - строго верхняя треугольная матрица. Асимптотический фактор сходимости этого метода обозначается а$ и оценивается сверху следующим образом1:

а5<р((/-|Ь|Гг(|Ь| + |и|)).

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

Г.Майер4 для неотрицательной интервальной матрицы А и неразложимой |А| получил результаты, аналогичные результатам для полношагового метода, доказал неравенство as < aj и достаточные условия выполнения строгого неравенства. Были получены также верхние оценки и неравенства для факторов сходимости различных итерационных процессов, но при более жестких условиях5.

Как и в случае полношагового метода при х* £ VF(A), итерационный процесс в пространстве Ш," в достаточно малой окрестности х* можно рассматривать как итерационный процесс в Ж2":

= + +Ь, к= 0,1,..., (11)

где для удобства рассуждений x^,b £ IR2" получены по формулам (9), а L,D,U€TR2nx2n, A{x*) = L + Ö + Uk

Нd')-u-{VU и")■

\ ь21 i/22 J \ и21 UVI J \ с'21 и22 /

ь^и^ще it*", i,j = 1,2,

Lij - строго нижние треугольные матрицы, Dij — диагональные матрицы, Uij - строго верхние треугольные матрицы, причем Lu, D\l, D22, Un, U22 — неотрицательные матрицы, Lu, ¿21, £>12, -D21, U21 — неположительные матрицы.

Утверждение 1.8.1 Если в сходящемся короткошаговом методе (10) х* € ЩА), moas = p ((/ - Ь)-\0 + U)).

Пусть L,D,U 6 Ж"*", и L - строго нижняя треугольная матрица, такая что /у = min |а,, |}, i > j, i,j = 1 ,п, D - диагональная матрица, такая что dy = min {1, jstfj-1}, i — j, i, j = 1, n, U - строго верхняя треугольная матрица, такая что йу = min {|a;j|, |ау |}, i < j,i,j=T~n.

4Mayer G. On a theorem of Stein-Rosenberg type in interval analysis. Numer. Math. 50 (1986), 17-26.

5Mayer G. Enclosing the solution of systems of linear equations by interval iterative processes. Computing, Suppl. 6 (1988), 47-58.

Теорема 1.8.1 Если в сходящемся коротпкошаговом методе (10) х* е ТУ(А), то а5>р ((/ - Ь)~1ф + #)) .

Далее в этом же параграфе доказываются аналоги оценок из §1.5 и результатов из §1.6. Предложенная методика позволяет сравнивать скорости сходимости различных методов.

Теорема 1.8.5 Если для системы (2) /э(]А|) <1 их* £ И7 (А), то а$ < ах -

В' §1.9 приводятся результаты для короткошагового метода релаксации, определяемого формулами

х(*+1) = (! _ ^(к) + ы (Ьх(*+Ч + р + и)х(Ч + Ь), " * = 0,1,..., (12).

где ш > 0 — релаксационный параметр, а матрицы Ь, и - те же, что и в методе (10). Известно1, что необходимое и достаточное условие сходимости метода (12) таково:

р ((/ - ИЧГ1 (|1 - ш\1++ |и|))) < 1. (13)

При этом, если метод (3) сходится и 0<^< 2/ (1+/>(|А|)), то метод (12) тоже сходится к неподвижной точке х*, для которой

х*=(1-о>)х*+ш (Ах*+Ь) =(1—и)х*+ш (Ьх*+(0+и)х*+Ь). (14)

Если 0 < и < 1, то неподвижные точки методов (3) и (12) совпадают: х* = х*. Если же и > 1, то х* С х*.

Для асимптотического фактора сходимости ая релаксационного метода (12) получены верхняя и нижняя оценки: при условии (13)

^ <р((1- *|ь|Гг (|1 - +<"(Р1 + |и|))),

при условиях 0<ш<1 и х* € И^(А)

ад >р((1- "¿Г1 ((1 - ш)1 + ыф + й))) , а также доказано утверждение о его точном значении: Утверждение 1.9.1 Если в сходящемся методе (12) х* 6 то

аЕ = р((1-шЬ)-1({1-и)1 + и(В + и))).

Здесь L,D,U, L,D,Ü — матрицы, описанные в §1.8.

Во второй главе рассматривается вопрос совпадения интервальной оболочки объединенного множества решений и неподвижной точки сжимающего интервального отображения.

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

Рассмотрим интервальную систему линейных алгебраических уравнений:

Аз; = ь, Аетпхл, belli" (15)

Одной из важных задач, связанных с системой (15), является задача нахождения объединенного множества решений (ОМР):

s = -{х\{за е А)(эь е ь)(л® = ь)}.

Интервальной оболочкой этого множества называется минимальный интервальный вектор Xя = (xf,хя,... ,хя)Т, содержащий Е:

xf = [xf,хя] , xf = min {x¡\x £ E}, xf = max {x¡\x G S},

i = 1,2,... ,n.

Нахождение Xя требует решения порядка 2"—2"2 точечных систем, а в случаях системы (15) с вещественной матрицей или монотонной интервальной матрицей А, вектор Xя может быть найден как решение двух неинтервальных систем или как результат умножения вещественной^ обратной матрицы на интервальный вектор 6 7. В общем случае при обращении только одной вещественной матрицы 8 не гарантируется получение минимального по ширине ограничения множества S.

Если систему (15) можно привести к равносильной (в смысле совпадения объединенных множеств решений Е i Б' соответственно) системе

X = Мх + г, (16)

6Beeck Н. Zur scharfen Außenabschätzung der Lösungsmenge bei linearen Intervallgleichungssystemen. ZAMM 54 (1974), 208-209.

7Beeck H. Bemerkungen zu Komponentenweisen Abschätzungen bei linearen Gleichungssystemen mit fehlerhaften Daten. ZAMM 57 (1977), 265-266.'

8Rohn J. Cheap and tight bounds: the recent result by E. Hansen can be made more efficient. Interval Computations 4 (1993), 13-21.

так, чтобы отображение Mi+r было сжимающим, то неподвижная точка х* этого отображения (алгебраическое решение уравнения (16) 9) всегда содержит интервальную оболочку Xя: Xя С х*. Таким образом, множество Е может быть ограничено каким-либо итерационным методом, а основная задача, рассматривающаяся во второй главе состоит в следующем:

при каких условиях алгебраическое решение х* системы х — Мж + г совпадает с интервальной оболочкой Xй объединенного множества решений равносильной системы А.х = Ъ?

Совпадение Xя и х* доказано1 для интервальных систем (16) с неотрицательной матрицей М. Достаточные условия совпадения Xя и х* доказаны Г.Майером5 для итерационных методов, основывающихся на подходящем М-расщеплении А = М — N М-матрицы А системы (15).

Тякжб в §2.1 для одного из способов приведения системы (15) к равносильному виду (16) доказывается выполнение неравенства />(|М|) < 1.

В §2.2 доказывается необходимое и достаточное условие совпадения Xя и х* для систем вида (16) со знакопостоянной матрицей.

Теорема 2.2.1 Пусть матрица М в системе (16) состоит только из неположительных и неотрицательных коэффициентов. Для того, чтобы интервальная оболочка Xs множества Е' совпадала с алгебраическим решением х* системы (16) достаточно, а если при i,j — 1 ,п выполняются требования Xя < хя и п^ ф [0,0], i ф j, то и необходимо, чтобы в матрице М:

1. главная диагональ была неотрицательная;

2. существовала строка i € {1,2,... ,п) такая что если знаки коэффициентов mlp и p.q = 1 ,п,р ф q, совпадают, то коэффициенты тР9 и тяр неотрицательны; в случае несовпадения таков

и т!Ч коэффициенты шрд и т9Р неположительны.

В этом же параграфе доказывается возможность при выполнении требований 1 и 2 теоремы 2.2.1 и условия 0 Е int(r;), i = 1 ,п получения вектора Xя путем решения двух вещественных систем с пх «-матрицами.

9Shary S. Algebraic approach in the "outer problem" for interval linear equation. Reliable Computing 3 (2) (1997) , 103-135.

В §2.3 необходимое и достаточное условие совпадения Xя и х* в случае х* £ PF(M) сформулировано по-другому.

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

Воспользуемся равенством (8) и, например, представлением (9) для определения коэффицентов матрицы М(х*).

Теорема 2.3.1 Пусть матрица М в системе (16) состоит только из неотрицательных и неположительных интервалов. Для того, чтобы интервальная оболочка Xя совпадала с алгебраическим решением х* системы (16) достаточно, а если при i,j — 1,п выполняются условия xf < х", и m,y ф [0,0],г j, то и необходимо, чтобы матрица М(х*) путем перестановок рядов i и i + п (i 6 {1,2,..., п}) приводилась к блочно диагональному виду с блоками пхп.

Доказано также простое и довольно легко проверяемое достаточное условие совпадения Xя и х* для произвольной системы (16).

Теорема 2.3.2 Пусть длях* выполняется равенство х* = Мх* + г, матрица М(х*) 6 Ж.2"*2" получена из интервальной матрицы М с помощью отображения о : I1R" ->■ Л2", заданного по формуле (9). Если матрица М(х*) путем перестановок рядов i ui + n (i £ {1,2,... ,п}) приводится к блочно диагональному виду с пхп-блоками, то Xя совпадает с х*.

Далее показано, что возможность приведения матрицы М(х*) к блочно диагональному виду с блоками одинаковой размерности не является в общем случае необходимым условием совпадениия Xя

И X*.'

В приложении приведены алгоритмы и программы, осуществляющие для некоторых теорем главы 1 проверку их условий.

Автор выражает глубокую признательность В.С.Зюзину, Т.Э.Каминскому, Л.В.Куприяновой, Г.Г.Меньшикову, В.М.Нестерову и С.П.Шарому.

Список работ по теме диссертации

[1] Кузнецова М.А. К вопросу об итерационном ограничении множества решений интервальной системы линейных алгебраических уравнений. JL, 1987. Деп. в ВИНИТИ, №1389-В87, 14с.

[2] Кузнецова М.А. Об одной частичной системе интервальной арифметики. Л., 1987. Деп. в ВИНИТИ, №2182-В87, 6с.

[3] Кузнецова М.А. Достаточное условие совпадения интервальной оболочки множества решений интервальной системы линейных алгебраических уравнений с ее итерационным решением. Л., 1987. Деп. в ВИНИТИ, №7836-В87, 8с.

[4] Кузнецова М.А. Нахождение интервальной оболочки множества решений интервальной системы линейных алгебраических уравнений (ИСЛАУ) итерационными методами. Препринт ВЦ СО АН СССР №, Красноярск, 1987.

[5] Ляшко М.А. Одна итерационная схема решения ИСЛАУ. Материалы Всесоюзной конференции "Актуальные проблемы прикладной математики". Саратов, 1991.

[6] Ляшко М.А. О совпадении интервальной оболочки объединенного множества решений ИСЛАУ с итерационным решением. Балашов, 1996. Деп. в ВИНИТИ, №429-В96, 16с.

[7] Ляшко М.А. О скорости сходимости полношагового итерационного метода для интервальных СЛАУ. Балашов, 1996. Деп. в ВИНИТИ, №430-В96, 22с.

[8] Lyashko М.А. On the speed of convergence of the total step iterative method for a class of interval linear algebraic systems. Reliable Computing 2 (4) 1996, 351-356.

[9] Ляшко М.А. Один способ нахождения асимптотического фактора сходимости полношагового итерационного метода для интервальных СЛАУ. Вычислительные технологии, 2, №1, 1997, 37-44.

[10] Ляшко М.А. Скорость сходимости интервальных итерационных методов. Балашов, 1997. Деп. в ВИНИТИ, №2692~В97, 53с.