Daí segue que α ≈ | φ ′ (ξ) | (\displaystyle \alpha \approx |\varphi "(\xi)|). Assim, para que o método convirja, é suficiente que ∀ x ∈ [ a , b ] | φ ′ (x) | ≤ 1. (\displaystyle \forall x\in \quad |\varphi "(x)|\leq 1.)

Algoritmo geral de aproximações sucessivas[ | ]

Aplicado ao caso geral de equações de operadores, esse método é chamado método de aproximações sucessivas ou método de iteração simples. No entanto, a equação pode ser transformada para o mapeamento de contração , que tem a mesma raiz, de maneiras diferentes. Isso dá origem a vários métodos particulares que têm taxas de convergência lineares e mais altas.

Conforme aplicado ao SLAU[ | ]

Considere o sistema:

( a 11 x 1 + … + a 1 n x n = b 1 … a n 1 x 1 + … + a n n x n = b n (\displaystyle \left\((\begin(array)(ccc)a_(11)x_(1)+) \ldots +a_(1n)x_(n)&=&b_(1)\\\ldots &&\\a_(n1)x_(1)+\ldots +a_(nn)x_(n)&=&b_(n) \end(array))\right.)

Para isso, o cálculo iterativo ficará assim:

(x 1 x 2 ⋮ x n) i + 1 = (a 11 + 1 a 12 … a 1 n a 21 a 22 + 1 … a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 … a n n + 1) (x 1 x 2) ) ⋮ x n) i − (b 1 b 2 ⋮ b n) (\displaystyle \left((\begin(array)(c)x_(1)\\x_(2)\\\vdots \\x_(n))\ end (array))\right)^(i+1)=\left((\begin(array)(cccc)a_(11)+1&a_(12)&\ldots &a_(1n)\\a_(21)&a_ ( 22)+1&\ldots &a_(2n)\\\vdots &\vdots &\ddots &\vdots \\a_(n1)&a_(n2)&\ldots &a_(nn)+1\end(array))\ right )\left((\begin(array)(c)x_(1)\\x_(2)\\\vdots \\x_(n)\end(array))\right)^(i)-\left ((\begin(array)(c)b_(1)\\b_(2)\\\vdots \\b_(n)\end(array))\right))

O método convergirá a uma taxa linear se ‖ a 11 + 1 … a 1 n ⋮ ⋱ ⋮ a n 1 … a n n + 1 ‖< 1 {\displaystyle \left\|{\begin{array}{ccc}a_{11}+1&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn}+1\end{array}}\right\|<1}

Barras verticais duplas significam alguma norma de matriz.

Solução da equação f(x)=0 pelo método de Newton, aproximação inicial: x 1 =a.

Método de Newton (método tangente)[ | ]

Caso unidimensional[ | ]

Otimizando a transformação da equação original f (x) = 0 (\displaystyle f(x)=0) em mapeamento de contração x = φ (x) (\displaystyle x=\varphi (x)) permite obter um método com uma taxa de convergência quadrática.

Para que o mapeamento seja mais eficiente, é necessário que no ponto da próxima iteração x ∗ (\displaystyle x^(*)) realizado φ ′ (x ∗) = 0 (\displaystyle \varphi "(x^(*))=0). Vamos procurar uma solução para esta equação na forma φ (x) = x + α (x) f (x) (\displaystyle \varphi (x)=x+\alpha (x)f(x)), então:

Vamos usar o que f (x) = 0 (\displaystyle f(x)=0), e obtemos a fórmula final para α (x) (\displaystyle \alpha (x)):

Com isso em mente, a função de contração terá a forma:

Então o algoritmo para encontrar uma solução numérica para a equação f (x) = 0 (\displaystyle f(x)=0) reduz a um procedimento de cálculo iterativo:

Métodos iterativos

Os métodos iterativos pressupõem a implementação das três etapas a seguir: construção de um processo iterativo convergindo para a solução exata para calcular aproximações sucessivas (ou seja, construir uma sequência de vetores convergindo para a solução exata ; determinação do critério de convergência deste processo, que permite determinar o momento de obtenção da precisão requerida; estudo da taxa de convergência e otimização do processo iterativo, a fim de reduzir o número de operações necessárias para atingir a precisão necessária.

Os métodos iterativos permitem obter uma solução com uma precisão pré-determinada, se for comprovada a convergência do método. Os métodos iterativos não fornecem uma solução estritamente exata, pois ela é alcançada como um limite de uma sequência de vetores. O método direto geralmente fornece uma solução exata, mas devido a erros de arredondamento que ocorrem em todos os computadores, ela não pode ser alcançada e a priorié até difícil avaliar o quanto essa solução difere da exata. Em conexão com o acima, os métodos iterativos às vezes permitem obter uma solução com maior precisão do que os diretos.

Considere vários métodos iterativos para resolver equações lineares.

Método de iteração simples

No método de iteração simples, o sistema (2.1) de equações algébricas lineares ax = bé reduzido a um sistema equivalente da forma

A solução do sistema (2.9) e, consequentemente, a solução do sistema original (2.1) é procurada como o limite da sequência de vetores para :

k = 0, 1, 2,…,(2.10)

onde é a aproximação inicial para o vetor solução.

Uma condição suficiente para a convergência do método de iteração simples é determinada pelo seguinte teorema.

TEOREMA 1. Se qualquer norma da matriz consistente com a norma considerada do vetor for menor que a unidade (), então a sequência no método de iteração simples converge para a solução exata do sistema (2.9) a uma taxa não menor que a taxa de uma progressão geométrica com denominador para qualquer aproximação inicial.

PROVA. Para provar o teorema, introduzimos um erro . Subtraindo a igualdade (2.10) da relação, obtemos . Passando para as normas, temos

Observe que a desigualdade da expressão anterior é a condição de consistência para a norma da matriz e do vetor. Se um , então para qualquer vetor de erro inicial (ou caso contrário, para qualquer vetor inicial ), a taxa de erro tende a zero não mais lenta do que uma progressão geométrica com o denominador .

Se escolhermos a norma como norma matricial ou então, para resolver a questão da convergência do método de iteração simples, pode-se usar o corolário do Teorema 1: o método de iteração simples converge se uma das seguintes condições for satisfeita para a matriz:

, i = 1,2, …, n,

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

A maneira mais simples e comum de trazer o sistema Ax=bà forma (2.9), conveniente para iterações, é a seleção de elementos diagonais, com cada i-ésimo a equação é resolvida em relação a i-ésimo desconhecido:

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

e o método de iteração simples pode ser escrito como

A matriz então tem a forma

.

O elemento desta matriz pode ser escrito como onde é o símbolo de Kronecker. Neste caso, uma condição suficiente para a convergência do método de iteração simples pode ser formulada como a condição para a dominância dos elementos diagonais da matriz MAS, que segue de (2.11) e a notação da matriz , i.e.

i = 1, 2, …, n.

Ressaltamos mais uma vez que as formas consideradas da condição para a convergência do método de iteração são apenas suficientes. Sua execução garante a convergência do método, mas sua falha no caso geral não significa que o método de iteração simples divirja. Uma condição necessária e suficiente para a convergência do método de iteração simples é a condição de que a parte inteira (onde é o valor próprio do módulo máximo da matriz MAS); esta condição raramente é usada na prática computacional.

Passemos à questão de estimar o erro da solução. De interesse são duas relações para estimar o erro da solução: a primeira relaciona a norma do erro à norma da diferença de duas aproximações sucessivas e pode ser utilizada para estimar o erro apenas no processo de cálculos; a segunda relaciona a norma do erro às normas do vetor da aproximação inicial e do vetor do termo livre no sistema (2.9). As relações necessárias são dadas pelos dois teoremas a seguir.

TEOREMA 2. Se alguma norma da matriz consistente com a norma considerada do vetor X

. (2.13)

PROVA. Vamos subtrair a igualdade (2.10) da igualdade:

Subtraindo de ambas as partes o valor de aproximação, transformamos esta razão na forma

Passando para as normas, obtemos

Uma vez que, pela hipótese do teorema,

Usando a relação da qual segue que finalmente obtemos:

TEOREMA 3. Se alguma norma é uma matriz consistente com a norma considerada do vetor X, menor que um (), então ocorre a seguinte estimativa de erro:

Vamos fazer duas observações. Primeiro, a relação (2.13) pode ser escrita como

o que permite obter uma estimativa do erro com base nos resultados das duas primeiras iterações. Primeiro, ao usar o método de iteração, às vezes é recomendável usar a norma da diferença de duas aproximações sucessivas como estimativa do erro de cálculo. Segue-se das correlações para o erro que isso não é verdade no caso geral. Se a norma estiver próxima da unidade, então o coeficiente at pode ser bastante grande.

Os erros de iterações sucessivas são relacionados pela relação

Essa. o erro muda linearmente em um passo. Diz-se que o método tem convergência linear ou convergência de primeira ordem. No entanto, o número de iterações necessárias para atingir a precisão necessária depende do valor e da aproximação inicial de .

Assim, usando o método de iteração simples como exemplo, são demonstradas três etapas dos métodos iterativos: construção de uma sequência de vetores gerados pela fórmula (1.10); determinação da condição de convergência de acordo com o Teorema 1 e uma estimativa da taxa de convergência usando os Teoremas 2 e 3.

Método Seidel

O método de iteração simples não usa a possibilidade aparentemente óbvia de melhorar a convergência do processo iterativo - a introdução imediata dos componentes recém-calculados do vetor no cálculo. Esta possibilidade é usada no método iterativo Seidel. O processo iterativo para o sistema (2.9) é realizado neste caso de acordo com a relação

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

ou para o sistema (1.1)

Sem entrar em detalhes, notamos que o método de iteração Seidel geralmente leva a uma convergência mais rápida do que o método de iteração simples. No entanto, há casos em que o método de iteração Seidel converge mais lentamente do que o método de iteração simples, e até mesmo casos em que o método de iteração simples converge, mas o método de iteração Seidel diverge.

Observe que o método Seidel converge, se matriz MAS definida positiva e simétrica.

Vamos mostrar que o método de iteração de Seidel é equivalente a algum método de iteração simples com uma matriz e um vetor especialmente construídos em relação (2.10). Para fazer isso, escrevemos o sistema (2.14) na forma Matriz (EH)é uma matriz triangular inferior com elementos diagonais iguais a um. Portanto, o determinante dessa matriz é diferente de zero (igual a um) e possui uma matriz inversa. Então

Comparando esta relação com a solução (2.10), podemos concluir que o método de iteração de Seidel é de fato equivalente ao método de iteração simples no sentido de que, para estabelecer a condição e o critério de convergência para o método de iteração de Seidel, pode-se usar os teoremas dados para o método de iteração simples, se definirmos O processo iterativo para o sistema (2.12) também pode ser escrito de uma forma mais geral, a saber

Seja um sistema de n equações algébricas com n incógnitas:

Algoritmo de método de iteração simples:

Observe que aqui e no que segue, o subscrito denota o componente correspondente do vetor de incógnitas, e o sobrescrito denota o número de iteração (aproximação).

Então um processo matemático cíclico é formado, cada ciclo do qual representa uma iteração. Como resultado de cada iteração, um novo valor do vetor de incógnitas é obtido. Para organizar o processo iterativo, escrevemos o sistema (1) na forma acima. Nesse caso, os termos da diagonal principal são normalizados e permanecem à esquerda do sinal de igual, enquanto os demais são transferidos para o lado direito. Sistema de equações reduzido parece:

notar que nunca será alcançado, no entanto, a cada iteração subsequente, o vetor de incógnitas se aproxima cada vez mais da solução exata.

12. A principal fórmula iterativa usada no método de iteração simples para resolver uma equação não linear:

13. Critério para parar o processo iterativo no método de iteração simples para resolver uma equação não linear:

O processo iterativo termina se para cada i-ésima componente do vetor de incógnitas a condição para alcançar a precisão for satisfeita.
notar que solução exata no método de iteração simples nunca será alcançado, no entanto, a cada iteração subsequente, o vetor de incógnitas está se aproximando cada vez mais da solução exata

14. Critérios para escolha da função auxiliar F(x) para o segmento de iteração do intervalo:

Ao realizar um teste matemático para resolver o método de iteração simples, a condição de convergência deve primeiro ser verificada. Para a convergência do método, é necessário e suficiente que na matriz A os valores absolutos de todos os elementos diagonais sejam maiores que a soma dos módulos de todos os outros elementos da linha correspondente:

Desvantagem dos métodos iterativos Esta é uma condição de convergência bastante rigorosa, que está longe de ser satisfeita para todos os sistemas de equações.

Se a condição de convergência for satisfeita, na próxima etapa é necessário definir a aproximação inicial do vetor de incógnitas, que geralmente é o vetor zero:

15. O método de Gauss usado para resolver sistemas de equações lineares prevê:

O método é baseado na transformação de matrizes para a forma triangular. Isto é conseguido pela eliminação sequencial das incógnitas das equações do sistema.

O método de iteração simples, também chamado de método de aproximação sucessiva, é um algoritmo matemático para encontrar o valor de uma quantidade desconhecida refinando-a gradualmente. A essência deste método é que, como o nome indica, gradualmente expressando os subsequentes da aproximação inicial, eles obtêm resultados cada vez mais refinados. Este método é usado para encontrar o valor de uma variável em uma determinada função, bem como na resolução de sistemas de equações, tanto lineares quanto não lineares.

Vamos considerar como esse método é implementado ao resolver o SLAE. O método de iteração simples tem o seguinte algoritmo:

1. Verificação da condição de convergência na matriz original. Teorema da convergência: se a matriz original do sistema tem dominância diagonal (ou seja, em cada linha, os elementos da diagonal principal devem ser maiores em módulo do que a soma dos elementos das diagonais laterais em módulo), então o método de simples iterações é convergente.

2. A matriz do sistema original nem sempre tem dominância diagonal. Nesses casos, o sistema pode ser modificado. As equações que satisfazem a condição de convergência são deixadas intocadas e, com aquelas que não satisfazem, formam combinações lineares, ou seja, multiplique, subtraia, adicione equações umas às outras até obter o resultado desejado.

Se no sistema resultante houver coeficientes inconvenientes na diagonal principal, então termos da forma c i * x i são adicionados a ambas as partes de tal equação, cujos sinais devem coincidir com os sinais dos elementos diagonais.

3. Transformação do sistema resultante para a forma normal:

x - =β - +α*x -

Isso pode ser feito de várias maneiras, por exemplo: da primeira equação, expresse x 1 em termos de outras incógnitas, da segunda - x 2, da terceira - x 3, etc. Aqui usamos as fórmulas:

α ij = -(a ij / a ii)

i = b i /a ii
Você deve novamente certificar-se de que o sistema resultante de forma normal satisfaça a condição de convergência:

∑ (j=1) |α ij |≤ 1, enquanto i= 1,2,...n

4. Começamos a aplicar, de fato, o próprio método das aproximações sucessivas.

x (0) - aproximação inicial, expressamos através dele x (1) , depois através de x (1) expressamos x (2) . A fórmula geral em forma de matriz é assim:

x (n) = β - +α*x (n-1)

Calculamos até atingirmos a precisão necessária:

max |x i (k)-x i (k+1) ≤ ε

Então, vamos ver o método de iteração simples na prática. Exemplo:
Resolva SLAE:

4,5x1-1,7x2+3,5x3=2
3,1x1+2,3x2-1,1x3=1
1,8x1+2,5x2+4,7x3=4 com precisão ε=10 -3

Vamos ver se os elementos diagonais predominam módulo.

Vemos que apenas a terceira equação satisfaz a condição de convergência. Transformamos a primeira e a segunda equações, adicionamos a segunda à primeira equação:

7,6x1+0,6x2+2,4x3=3

Subtraia o primeiro do terceiro:

2,7x1+4,2x2+1,2x3=2

Convertemos o sistema original em um equivalente:

7,6x1+0,6x2+2,4x3=3
-2,7x1+4,2x2+1,2x3=2
1,8x1+2,5x2+4,7x3=4

Agora vamos trazer o sistema de volta ao normal:

x1=0,3947-0,0789x2-0,3158x3
x2=0,4762+0,6429x1-0,2857x3
x3= 0,8511-0,383x1-0,5319x2

Verificamos a convergência do processo iterativo:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0,383+ 0,5319= 0,9149 ≤ 1, ou seja. a condição é satisfeita.

0,3947
Suposição inicial x(0) = 0,4762
0,8511

Substituindo esses valores na equação da forma normal, obtemos os seguintes valores:

0,08835
x(1) = 0,486793
0,446639

Substituindo os novos valores, temos:

0,215243
x(2) = 0,405396
0,558336

Continuamos os cálculos até chegarmos mais perto dos valores que satisfazem a condição dada.

x(7) = 0,441091

Vamos verificar a exatidão dos resultados obtidos:

4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3,1*0,1880+2,3*0,441-1,1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977

Os resultados obtidos substituindo os valores encontrados nas equações originais satisfazem totalmente as condições da equação.

Como podemos ver, o método de iteração simples fornece resultados bastante precisos, no entanto, para resolver essa equação, tivemos que gastar muito tempo e fazer cálculos complicados.