3.6. Задания#

3.6.1. Прямая и обратная подстановка#

Реализуйте прямую и обратную подстановки для решения треугольных систем

\[\begin{split} \mathbf{L} x = \mathbf{b} \\ \mathbf{U} x = \mathbf{b} \end{split}\]

где \(\mathbf{L}\) и \(\mathbf{U}\) квадратные нижнетреугольная и верхнетреугольная матрицы, соответственно, а \(\mathbf{b}\) – вектор правой части системы.

Функция должны иметь следующую сигнатуру вызова

function forwardsub(L::AbstractMatrix, b::AbstractVector) end
function backwardsub(U::AbstractMatrix, b::AbstractVector) end

а возвращать вектор из Float64 чисел.

Добавьте в функции несколько проверок

  1. На размерность — матрица квадратная, размер матрицы системы и правой части корректны;

  2. На треугольность системы (см. Julia/LinearAlgebra);

  3. На вырожденность системы.

Дополнительно

  • Напишите doc-string к каждой из функций (см. Julia/Documentation);

  • Напишите версии функций, не аллоцирующих память под вектор-решение \(x\), а принимающих вектор на запись ответа в качестве аргумента:

    • forwardsub!(x, L, b),

    • backwardsub!(x, U, b).

3.6.2. Метод прогонки#

При численном решении дифференциальных уравнений часто возникает система

\[ a_i x_{i-1} + b_i x_i + c_i x_{i+1} = f_i, \quad i=1,\ldots,n, \]

где \(a_1 = c_n = 0\), а \(\mathbf{f}\) – вектор правой части системы.

В матричном виде система записывается как \(\mathbf{A} \mathbf{x} = \mathbf{f}\), где матрица системы — трёхдиагональная

\[\begin{split} \begin{bmatrix} b_1 & c_1 & & & & \\ a_2 & b_2 & c_2 & & & \\ & a_3 & b_3 & c_3 & & \\ & & \ddots & \ddots & \ddots & \\ & & & a_{n-1} & b_{n-1} & c_{n-1} \\ & & & & a_n & b_n \end{bmatrix} \end{split}\]

Для таких систем существует эффективный \(O(n)\) алгоритм решения, называемый методом прогонки или алгоритмом Томаса.

Напишите функцию tridiagsolve, реализующую метод прогонки. У функции должно быть два метода

  • tridiagsolve(a, b, c, f) -> x;

  • tridiagsolve(A::Tridiagonal, f) -> x, где Tridiagonal тип определён в LinearAlgebra.

Описание метода прогонки можно посмотреть здесь: [16] (Раздел 4.4.2), Википедия.

3.6.3. Системы уравнений#

Решите следующие системы уравнений. Для каждого примера создайте функцию, которая не принимает аргументов и возвращает решение системы и невязку \(\mathbf{b} - \mathbf{A}\mathbf{x}\).

Например,

function solution_a()
    A = [1 0; 0 1]
    b = [3, 4]
    x = A \ x
    return x, b - A * x
end

(а)

\[\begin{split} \begin{bmatrix} 8 & 9 & 4 & -1 \\ 0 & 4 & 1 & 0 \\ 0 & 0 & -1 & 6 \\ 0 & 0 & 0 & 11 \\ \end{bmatrix} \mathbf{x} = \begin{bmatrix} 9 \\ 3 \\ -1 \\ 2 \\ \end{bmatrix} \end{split}\]

(б)

\[\begin{split} \begin{bmatrix} -2 & 1 & 0 & 0 & 0 \\ 1 & -2 & 1 & 0 & 0 \\ 0 & 1 & -2 & 1 & 0 \\ 0 & 0 & 1 & -2 & 1 \\ 0 & 0 & 0 & 1 & -2 \\ \end{bmatrix} \mathbf{x} = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ \end{bmatrix} \end{split}\]

(в)

\[\begin{split} \begin{bmatrix} 1 & 8 & -3 & 9 \\ 0 & 4 & 10 & -2 \\ 8 & 2 & -5 & 1 \\ 3 & 1 & 6 & 12 \\ \end{bmatrix} \mathbf{x} = \begin{bmatrix} 3 \\ 6 \\ 1 \\ 4 \\ \end{bmatrix} \end{split}\]