Дискретно-непрерывная математика (стр. 104 )

.

Если полношаговый метод сходится и ω удовлетворяет приведенному неравенству, то метод релаксации тоже сходится к неподвижной точке удовлетворяющей урав­нению

Эта неподвижная точка, вообще говоря, отлична от непо­движной точки уравнения Чтобы показать это, заметим сначала, что для всех вещественных чисел а, b и не­вырожденных интервалов Z (т. е. таких Z, что при ab>0 выполнено соотношение

Пусть Тогда имеем

т. е. так как неподвижная точкавычисленная методом релаксации, единственна.

Если же, напротив, мы имеем ω > 1, то

Если мы возьмем начальное приближение для метода релаксации, то из этого включения и монотонности вклю­чения следует, что

С помощью математической индукции можно показать, что

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

и дает достаточно хорошую локализацию.

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

а для метода релаксации — равенство

откуда следует, что Таким образом, для случая точечной матрицы и точечного вектора оба метода сходятся к ре­шению

уравнения

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

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

применением итерационного метода

и для которыхТогда величина

называется асимптотическим фактором сходимости этого итера­ционного метода в точке

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

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

Теорема 2. Пусть задано уравнение

для точечной матрицы такой что

и точечного вектора Тогда асимптотический фактор сходимости для полношагового метода (2, микромодуль 31) удовлетворяет равенству

а асимптотический фактор сходимости для метода релакса­ции — равенству

для

Доказательство. Проведем рассуждение для метода релакса­ции. Начав с произвольного интервального вектора мы с помощью (12, микромодуль 29) и (19, микромодуль 29) получаем из нашей итерационной формулы

что

или

Отсюда непосредственно получаем, что

Если теперь выбрать конкретный вектор х(0) так, что —

собственный вектор неотрицательной матрицы

, соответствующий собственному числу λ, равному спектральному радиусу этой матрицы, то из уравнения для следует, что

откуда получается нужное утверждение. Доказательство для полношагового метода можно провести аналогично.

Только что доказанная теорема позволяет сформулировать утверждение об асимптотически наискорейшем (в смысле опре­деления 1) методе.

Теорема 3. В условиях теоремы 2

а также

Доказательство. Рассмотрим вещественную точечную ма­трицу

и ее разложениегде

Это разложение регулярно, так как существует и Если ω удовлетворяет неравенству

и в силу неравенства мы получаем, что

Этим доказана первая часть теоремы. Ее вторая часть сле­дует из теоремы Штейна и Розенберга и ее обобщения, утверждающего, что из следует

В предыдущей теореме утверждается, что в случае системы точечных уравнений невозможно асимптотически (в смысле опре­деления 1) ускорить сходимость короткошагового метода, ис­пользуя метод релаксации. Кроме того, короткошаговый метод сходится не медленнее, чем полношаговый.

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