Sistema de resolução de equações lineares com matriz tridiagonal cíclica

Eu tenho esse problema no meu livro:

Sugira um algoritmo eficiente para resolver sistemas de equações lineares com matriz tridimensional cíclica, que é da forma: sem trocar nenhuma linha e coluna. Estimar a complexidade.
$[\begin{matrix} a_{1} & b_{1} & 0 & \dots & 0 & d_{1} \\ c_{2} & a_{2} & b_{2} & 0 & ⋮ & 0 \\ 0 & ⋱ & ⋱ & ⋱ & 0 & ⋮ \\ ⋮ & ⋮ & c_{n - 2} & a_{n - 2} & b_{n - 2} & 0 \\ 0 & \dots & \dots & c_{n - 1} & a_{n - 1} & b_{n - 1} \\ d_{2} & 0 & \dots & 0 & c_{n} & a_{n} \end{matrix}]$ $\begin{bmatrix} a_1&b_1&0&\cdots&0&d_1\\c_2&a_2&b_2&0&\vdots&0\\0&\ddots&\ddots&\ddots&0&\vdots\\\vdots&\vdots&c_{n-2}&a_{n-2}&b_{n-2}&0\\0&\cdots&\cdots&c_{n-1}&a_{n-1}&b_{n-1}\\d_2&0&\cdots&0&c_n&a_n\end{bmatrix}$

E eu não sei como abordar isso. Eliminação clássico iria trabalhar em muito eficiente o tempo com esta matriz, mas o problema é quando, digamos, quero eliminar com linha -st que é add a segunda linha e quando . Não posso fazer isso e, mesmo que , o mesmo problema possa ocorrer em algum lugar no meio desse processo. Além disso, como o texto do problema declara, não tenho permissão para trocar nenhuma linha ou coluna; portanto, não sei se essa abordagem pode ser corrigida de alguma forma. Alguém pode ajudar? $O(n)$ $c_{2}$ $1$ $\frac{-c_{2}}{a_{1}}\cdot \begin{bmatrix} a_1&b_1&0&\cdots&0&d_1 \end{bmatrix}$ $a_1=0$ $a_1\neq 0$

matrix linear-solver xan
fonte

A forma da matriz não impedirá que você encontre um problema com a matriz (ou uma submatriz) sendo singular, mas eu não leio o problema perguntando sobre o que pode dar errado. Em vez disso, solicitando um "algoritmo eficiente ... sem trocar nenhuma linha e coluna", parece que sua "eliminação cássica" sem pivotamento seria uma abordagem razoável. Você vê como estimar a complexidade desse método?

hardmath

Respostas:

Não é difícil determinar a complexidade de uma eliminação / redução direta para a forma triangular superior. Observe que a matriz inicial:

[\begin{matrix} a_{1} & b_{1} & 0 & \dots & 0 & d_{1} \\ c_{2} & a_{2} & b_{2} & 0 & ⋮ & 0 \\ 0 & ⋱ & ⋱ & ⋱ & 0 & ⋮ \\ ⋮ & ⋮ & c_{n - 2} & a_{n - 2} & b_{n - 2} & 0 \\ 0 & \dots & \dots & c_{n - 1} & a_{n - 1} & b_{n - 1} \\ d_{2} & 0 & \dots & 0 & c_{n} & a_{n} \end{matrix}]

$\begin{bmatrix} a_1&b_1&0&\cdots&0&d_1\\c_2&a_2&b_2&0&\vdots&0\\0&\ddots&\ddots&\ddots&0&\vdots\\\vdots&\vdots&c_{n-2}&a_{n-2}&b_{n-2}&0\\0&\cdots&\cdots&c_{n-1}&a_{n-1}&b_{n-1}\\d_2&0&\cdots&0&c_n&a_n\end{bmatrix}$

torna-se após um passo de eliminação:

[\begin{matrix} a_{1} & b_{1} & 0 & \dots & 0 & d_{1} \\ 0 & a_{2} - \frac{b_{1} c_{2}}{a_{1}} & b_{2} & 0 & ⋮ & - \frac{d_{1} c_{2}}{a_{1}} \\ 0 & ⋱ & ⋱ & ⋱ & 0 & ⋮ \\ ⋮ & ⋮ & c_{n - 2} & a_{n - 2} & b_{n - 2} & 0 \\ 0 & \dots & \dots & c_{n - 1} & a_{n - 1} & b_{n - 1} \\ 0 & - \frac{b_{1} d_{2}}{a_{1}} & \dots & 0 & c_{n} & a_{n} - \frac{d_{1} d_{2}}{a_{1}} \end{matrix}]

$\begin{bmatrix} a_1&b_1&0&\cdots&0&d_1\\ 0 &a_2 - \frac{b_1 c_2}{a_1}&b_2&0&\vdots&-\frac{d_1 c_2}{a_1}\\0&\ddots&\ddots&\ddots&0&\vdots\\\vdots&\vdots&c_{n-2}&a_{n-2}&b_{n-2}&0\\0&\cdots&\cdots&c_{n-1}&a_{n-1}&b_{n-1}\\0&-\frac{b_1 d_2}{a_1}&\cdots&0&c_n&a_n-\frac{d_1 d_2}{a_1}\end{bmatrix}$

O custo dessa etapa é constante e deixa uma submatriz cíclica de três diagonais cíclica no canto inferior direito. A redução total implicará, assim, custo. Para resolver um sistema linear, pode-se executar as mesmas operações no lado direito, também com um custo de . Também é necessário executar uma resolução traseira com uma matriz triangular superior com no máximo três entradas diferentes de zero por linha, outra tarefa . Isso representa a complexidade de resolver sistemas com essas matrizes de coeficientes. $O(1)$ $(n-1)\times(n-1)$ $O(n)$ $O(n)$ $O(n)$

hardmath
fonte

+1, obrigado, mas e se ? Então o primeiro passo será diferente. E pode haver complicações ainda mais. Isso não é um problema?

a_{1} = 0

$a_1=0$

xan

É uma limitação da eliminação gaussiana sem girar que, quando zeros aparecem em locais onde queremos (em essência) produzir um líder, ficamos presos! A idéia de rotação parcial está tentando contornar isso trocando linhas taticamente (respectivamente, linhas e colunas de troca dinâmica completa). Mas a declaração do problema proíbe a troca de linhas ou colunas, que eu interpreto como uma tentativa de manter sua análise da complexidade o mais simples possível. Certas condições (como dominância diagonal ) podem manter e garantir o sucesso sem girar.

hardmath