Метод минимальных поправок. 1. Задаем вектор х0 (начальное приближение), матрицу B = BT > 0.

1. Задаем вектор х₀ (начальное приближение), матрицу B = B^T > 0.

2. Положим x_k = x₀, k = 0 (номер итерации)

3. Вычисляем вектор r_k = Ax_k – b (невязка начального приближения).

4. Вычисляем вектор ω_k = r_kB_k^-1.

5. Вычисляем скаляр τ_k+1 = (Aω_k, ω_k) / (B^-1Aω_k, Aω_k) (шаговый множитель).

6. Вычисляем вектор x_k+1 = x_k – τ_k+1 B^-1Aω_k (очередное приближение).

7. Вычисляем вектор r_k+1 = Ax_k+1 – b. (невязка k+1 приближения).

8. Положим k = k + 1.

9. Проверяем выполнение неравенства ||r_k||₂ =< 0.001; если «да», то останавливаем работу алгоритма и выводим результаты, иначе возвращаемся к шагу 3.

Рис.2 Блок-схема метода минимальных поправок

 

Метод скорейшего спуска

1. Задаем вектор х⁽⁰⁾ (начальное приближение).

2. Положим x_k = x₀, k = 0 (номер итерации)

3. Вычисляем вектор r_k = Ax_k – b (невязка начального приближения).

4. Вычисляем скаляр τ_k+1 = (r_k, r_k) / (Ar_k, Ar_k) (шаговый множитель).

5. Вычисляем вектор x_k+1 = x_k – τ_k+1r_k (очередное приближение).

6. Вычисляем вектор r_k+1 = Ax_k+1 – b. (невязка k+1 приближения).

7. Положим k = k + 1.

8. Проверяем выполнение неравенства ||r_k||₂ =< 0.001; если «да», то останавливаем работу алгоритма и выводим результаты, иначе возвращаемся к шагу 3.

Рис.3 Блок-схема метода скорейшего спуска

Метод сопряженных градиентов

1. Задаем вектор х₍₀₎ (начальное приближение).

2. Положим x_k = x₀, k = 0 (номер итерации)

3. Вычисляем вектор r_k = Ax_k – b (невязка начального приближения).

4. Положим вектор p_k= r_k (сопряженный вектор)

5. Вычисляем скаляр α_k = (r_k, r_k) / (Ap_k, p_k).

6. Вычисляем вектор x_k+1 = x_k + α_k p_k (очередное приближение)

7. Вычисляем вектор r_k+1 = r_k - α_k Ap_k. (невязка k+1 приближения)

8. Вычисляем скаляр β_k = (r_k+1, r_k+1) / (r_k, r_k).

9. Проверяем выполнение неравенства ||r_k+1||₂ =< 0.001; если «да», то останавливаем работу алгоритма и выводим результаты

10.. Вычисляем p_k+1= r_k+1+ β_kp_k

11. Положим k = k + 1.

12. Возвращаемся к шагу 5

Рис.4 Блок-схема метода сопряжённых градиентов

Руководство пользователя.

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

Рис.5 Окно программы

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

Рис.6 Решение системы с матрицей размерностью 10х10

Матрицу можно модифицировать, прибавив к главной диагонали заданную величину, для этого нужно ввести необходимую величину в поле «Преобладание», поставить флаг «Модифицировать» и нажать ОК.

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