Реферат: Алгоритм компактного хранения и решения СЛАУ высокого порядка

Ах=b,    (14)

Предполагая, что диагональные элементы aii  0 (i = 2, ..., n), выразим xi через первое уравнение систем x2 - через второе уравнение и т. д. В результате получим систему, эквивалентную системе (14):

Обозначим ; , где i == 1, 2, ...,n; j == 1,2,..., n. Тогда система (15) запишется таким образом в матричной форме

Решим систему (16) методом последовательных приближений. За нулевое приближение примем столбец свободных членов. Любое (k+1)-е приближение вычисляют по формуле

Если последовательность приближений x(0),...,x(k) имеет предел , то этот предел является решением системы (15), поскольку в силу свойства предела , т.е.  [4,6].

Метод Зейделя.

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

Пусть дана линейная система, приведенная к нормальному виду:

    (17)

Выбираем произвольно начальные приближения неизвестных и подставляем в первое уравнение системы (17). Полученное первое приближение подставляем во второе уравнение системы и так далее до последнего уравнения. Аналогично строим вторые, третьи и т.д. итерации.

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

где k=0,1,...,n

Метод Ланцоша.

Для решения СЛАУ высокого порядка (1), матрица, коэффициентов которой хранится в компактном  нижеописанном виде, наиболее удобным итерационным методом является метод Ланцоша [4], схема которого имеет вид:

      (18)

где

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

,           (19)

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

            (20)

Среднеквадратичную разность необходимо контролировать при выполнении каждых k наперед заданных итераций.