2. Математическая постановка задачи и описание метода

2.1 Математическая постановка задачи

Исследовать метод простой итерации для решения систем линейных алгебраических уравнений, а именно: влияние способа перехода от системы F(x)=x к системе x=(x) на точность полученного решения, скорость сходимости метода, время счета, число операций.

2.2 Описание метода

Пусть дана система линейных алгебраических уравнений в виде Ax=b (2.2.1).

Пусть (2.2.1.) приведена каким-либо образом к виду x=Cx+f (2.2.2), где C - некоторая матрица, f - вектор-столбец. Исходя из произвольного вектора

x⁰₁

x^{( 0 )}= x⁰₂

x⁰₃

строим итерационный процесс x^{( k+1 )}=Cx^{( k )}+f (k=0,1,2,3,…) или в развернутой форме

x₁ ^{( k+1 )} = c₁₁ x₁^{( k )} + c₁₂ x₂^{( k )} + …+ c_1n x_n^{( k )} + f₁ , (2.2.3)

x_n ^{( k+1 )} = c_n1 x₁^{( k )} + c_n2 x₂^{( k )} + …+ _1nn x_n^{( k )} + f_{n .}

Производя итерации, получим последовательность векторов x^{( 1 )}, x^{( 2)},…, x^{( k )},… Доказано, что если элементы матрицы C удовлетворяют одному из условий

 (i=1,2,…,n) (2.2.4)

(j=1,2,…,n) (2.2.5),

то процесс итерации сходится к точному решению системы x при любом начальном векторе x⁽⁰⁾, то есть

x=x^{( k )} .

Таким образом, точное решение системы получается лишь в результате бесконечного процесса, и всякий вектор x^(k) из полученной последовательности является приближенным решением. Оценка погрешности этого приближенного решения x^(k) дается одной из следующих формул:

| x_i - x_i^{( k )} | | x_i^{( k )} - x_i^{( k -1 )}|, (2.2.4)

если выполнено условие (2.2.4), или

| x_i - x_i^{( k )} | | x_i^{( k )} - x_i^{( k -1 )}|, (2.2.5)

если выполнено условие (2.2.5). Эти оценки можно еще усилить соответственно так:

max | x_i - x_i^{( k )} | | x_i^{( k )} - x_i^{( k -1 )}|, (2.2.4)

или

| x_i - x_i^{( k )} | | x_i^{( k )} - x_i^{( k -1 )}|. (2.2.5)

Процесс итераций заканчивают, когда указанные оценки свидетельствуют о достижении заданной точности.

Начальный вектор x^{( 0 )} может быть выбран, вообще говоря, произвольно. Иногда берут x^{( 0 )}=f. Однако, наиболее целесообразно в качестве компонент вектора x^{( 0 )} взять приближенные значения неизвестных, полученные грубой прикидкой.

Приведение системы (2.2.1) к виду (2.2.2) можно осуществить различными способами. Важно только, чтобы выполнялось одно из условий (2.2.4) или (2.2.5). Ограничимся рассмотрением двух таких способов.

Первый способ. Если диагональные элементы матрицы А отличны от нуля, то есть

a_ii0 ( i=1,2,…,n),

то систему (2.2.1) можно записать в виде

x₁= (b₁ - a₁₂ x₂ - … - a_1n x_n ),

x₂= (b₂ - a₂₁ x₁ - a₂₃ x₃ -… - a_2n x_n ), (2.2.6)

x_n= (b_n - a_n1 x₁ - … - a_{n n-1} x_n-1 ).

В этом случае элементы матрицы С определяются следующим образом:

(ij), c_ii=0,

и тогда условия (2.2.4) и (2.2.5) соответственно приобретают вид

(i=1,2,… ,n), (2.2.7)

(j=1,2,… ,n). (2.2.8)

Неравенства (2.2.7), (2.2.8) будут выполнены, если диагональные элементы матрицы А удовлетворяют условию

(i=1,2,… ,n), (2.2.9)

то есть если модули диагональных коэффициентов для каждого уравнения системы больше суммы модулей всех остальных коэффициентов (не считая свободных членов).

Второй способ позволяет записать систему (2.2.1) в виде

x₁ = b₁ - (a₁₁ -1)x₁ - a₁₂ x₂ - … - a_1n x_n ,

x₂ = b₂ - a₂₁ x₁ -(a₂₂ -1)x₂ -… - a_2n x_n , (2.2.10)

x_n = b_n - a_n1 x₁ - a_n2 x₂ - … -(a_nn -1)x_n .

и пояснений не требует.