Численное решение СЛАУ методом верхней релаксации

[ElRomcho]

Здравствуйте! Мне было дано задание численно решить данную СЛАУ:

$$\[-\gamma y_{i-1} + 2y_i + \gamma y_{i+1} = f_i, i=1,..., N-1\] \[y_0 = f_0,y_N = f_N,\] где $1 \leq \gamma \leq \frac{3}{2}$,\\ \begin{equation} f_i = \begin{cases} 0, \hspace{2pt} i = 0,...,60 \\ 0.1, \hspace{2pt} i = 61,...,70 \\ 0, \hspace{2pt} i = 71,..., N \end{cases} N = 100, 1000 \end{equation}$$

то есть матрица системы имеет вид:

$$\[A = \begin{bmatrix} 1 & 0 & 0 & \cdots & 0 & 0 & 0\\ - \gamma & 2 & \gamma & \cdots & 0 & 0 & 0\\ & & \cdots & \cdots & \cdots \\ 0 & 0 & 0 & \cdots & - \gamma & 2 & \gamma\\ 0 & 0 & 0 & \cdots & 0 & 0 & 1\\ \end{bmatrix}\]$$

В качестве метода я выбрал метод верхней релаксации. Была написана программа, которая даже выдавала корректный результат (выбранный релаксационный параметр - $\omega = 0.7$, в качестве начального приближения - вектор правой части). Но вот в чем проблема: не выполнено достаточное условие сходимости данного метода: $A = A^*$ и, более того, с данными ограничениями на значение $\gamma$ у матрицы отсутствует диагональное преобладание. Поэтому у проверяющего вполне обоснованно возник вопрос о корректности применения данного метода и выбора релаксационного параметра. И у меня возникли трудности с обоснованием корректности применения метода с выбранным параметром. Можете, пожалуйста, дать подсказку, куда копать? И я правильно понимаю, что для метода прогонки для решения этой задачи тоже не выполнено достаточное условие корректности и устойчивости к ошибкам округления, так как $2 < 2\gamma$? Возможно ли здесь применение метода прогонки вместо метода верхней релаксации? Спасибо!

[TOTAL]

ElRomcho в сообщении #1574730 писал(а):

Возможно ли здесь применение метода прогонки вместо метода верхней релаксации?

Возможно применение метода прогонки. Поищите про немонотонную прогонку.

[GAA]

А зачем в данной задаче немонотонная прогонка? (Немонотонная прогонка более «тяжёлая» в отношении вычислений, т.к. имеет проверки и переходы.)

«Диагональное преобладание» является достаточным, но не необходимым условием ненакопления погрешности вычислений. Для ненакопления погрешности достаточно, чтобы $|\alpha_i| < 1$ (для всех $i$).

Выполнив прямой ход Гаусса для небольших значений $N$, видим, что искать решение удобно в виде $y_i = -\alpha_{i+1}y_{i+1} + \beta_{i+1}$.
Подставив это выражение в $y_{i-1} = -\alpha_i y_i + \beta_i$, получим $y_{i-1} = \alpha_i \alpha_{i+1} y_{i+1} - \alpha_i \beta_{i+1} + \beta_i$.
Затем подставив эти выражения для $y_i$ и $y_{i-1}$ в разностное уравнение и приравняв коэффициенты нулю, получим выражения для коэффициентов прогонки:
$\alpha_{i+1} = \frac {\gamma/2}{1+\frac {\gamma} 2 \alpha_i}$, $\beta_{i+1} = \frac {f_i +\gamma \beta_i} {2+\gamma \alpha_i }$, $i = 1,2,\ldots N-1$.
Из условия $y_0 = f_0$ вытекает $\alpha_1 = 0$, $\beta_1 = f_0$.

Т.к. $0<\gamma/2<1$, то $|\alpha_i| < 1$.

(Коэффициенты прогонки, конечно нужно проверить. Я к вечеру устал и мог ошибиться. Но в случае $\alpha_i$ вроде ошибки не нашёл.)

[TOTAL]

GAA в сообщении #1574767 писал(а):

«Диагональное преобладание» является достаточным, но не необходимым условием ненакопления погрешности вычислений. Для ненакопления погрешности достаточно, чтобы $|\alpha_i| < 1$ (для всех $i$).

Действительно, это условие выполнится при обычной прогонке.

А ещё можно так:

$$A*t/\gamma=B*C,\;\; t=\dfrac{\gamma}{1+\sqrt{1+\gamma^2}}$$

В матрицах $B$ и $C$ на главной диагонали единицы, у $B$ стоит $t$ над диагональю, а у $C$ стоит $-t$ под диагональю. (В первых и последних строка чуть другое)

[ElRomcho]

Спасибо! Сегодня постараюсь реализовать метод прогонки.