FICHA 3, Metodos Numericos

Prévia do material em texto

Métodos Numéricos, 2018, Docente: Zacarias Mutombene Page 1 
 
Universidade Eduardo Mondlane 
Faculdade de Engenharias 
 
Curso de Licenciatura Engenharia Ambiental, Civil, Electrónica, 
Elétrica, Informática, Mecânica e Química 
2º Ano, 2º Semestre, Ano Lectivo 2018 
Capítulo 3: Resolução de Sistemas de Equações Lineares 
Introdução 
Considere o sistema de equações lineares de forma: 
AX = B (1) 
Sendo A uma matriz de dimensão nxn dos números reais, X e B vectores no espaço vectorial Rⁿ. 
Da álgebra sabe-se que o método de Crammer que resolve este sistema calcula-se da seguinte 
forma: 
 detA=|
 
 
 
| 
 Se detA , o sistema tem soluções 
 
 
. Sendo , o determinante respectivo 
ao Xi obtido pela substituição do vector B na coluna i-esima da matriz A. 
 Se detA , nesse caso se existe pelo menos um determinante o sistema (1) é 
incompatível. Se todos , o sistema tem infinidade de soluções. 
Este método tem uma grande desvantagem quando a dimensão do sistema é grande. Por 
exemplo, se n=20 temos que calcular 21 determinantes de ordem 20x20,o número de 
multiplicações a efectuar será 21x20! Mais um número semelhante de adições. 
Mas existem vários métodos para resolver o sistema (1), dividimos esses métodos em 2 grupos: 
 Métodos directos (dão solução exacta) tais como: Gauss, Gauss com Pivô, Jordan, 
decomposição LU, etc. 
 Métodos iterativos (dão soluções aproximadas) tais como: iterativo geral, Jacobi, Gauss-
Zeidel, etc. 
Métodos Numéricos, 2018, Docente: Zacarias Mutombene Page 2 
 
Métodos Directos 
São os que dão a solução exacta. 
1. Método GAUSS 
O método de Gauss consiste em duas etapas: 
1ª Etapa: Transformar o sistema (1) para a forma triangular superior: 
(
 
 
) ( ) 
2ª Etapa: Resolver o sistema triangular superior obtido da 1ª etapa a partir da 
última equação. 
A 1ª etapa 
O seguinte teorema é a base matemática das transformações na primeira etapa. 
Teorema: Se multiplicar uma equação do sistema (1) por uma constante 
somando a uma outra equação do sistema, obtém-se um novo sistema equivalente 
ao anterior. 
Fórmula geral das transformações da 1ª etapa 
Seja 
( )
 um elemento da linha , coluna e passo . 
 
( )
 
( )
 
 
( )
 
( )
 
( )
 
Onde: 
 
 
 
Exemplo: 
Resolver o seguinte sistema pelo método de Gauss: 
{
 
 
 
 
Os cálculos são representados na tabela: 
Métodos Numéricos, 2018, Docente: Zacarias Mutombene Page 3 
 
X1 X 2 X 3 B 
1 
1 
3 
2 
-1 
-6 
5 
3 
-1 
-9 
2 
25 
 1 
0 
0 
2 
-3 
-12 
5 
-2 
-16 
-9 
11 
52 
1 
0 
0 
2 
-3 
0 
5 
-2 
-8 
-9 
11 
8 
 
O sistema no passo 2 é: 
{
 
 
 
 
 
2. Gauss com Pivô (Parcial) 
Pivô da coluna no passo {| 
( )
|} 
Onde 
Se o pivô não está na diagonal a que trocar. 
Vantagem: Evitar acumulação de erros. 
Exemplo: 
Retomemos o exemplo no método Gauss, a tabela inicial é igual: 
X1 X 2 X 3 B 
 1 
1 
3 
2 
-1 
-6 
5 
3 
-1 
-9 
2 
25 
 
 
 
Pivô completo: 
Se 𝑀𝑎𝑥 |𝑎𝑖𝑗
(𝑘 )
| |𝑎𝑚𝑠
(𝑘 )
| 
Então pivô=𝑎𝑚𝑠
(𝑘 )
. E possível 
trocar linha e colunas. 
 
Passo inicial 
 
Passo 1 
 
Passo 2 
 
 
Métodos Numéricos, 2018, Docente: Zacarias Mutombene Page 4 
 
i,j≤k 
 
O pivô esta na posição a31, faz se a troca da 1ª e 3ª linha. 
3 
1 
1 
-6 
-1 
2 
-1 
3 
5 
25 
2 
-9 
 
Eliminar os elementos a21 e a31 (coluna 1, excepto a11) 
3 
0 
0 
-6 
+3 
12 
-1 
10 
16 
25 
19 
-52 
 
 
Na segunda coluna 4 é pivô, trocam-se as linhas 2ª e 3ª. 
3 
0 
 
0 
-6 
4 
 
+1 
-1 
 
 
 
 
 
 
25 
 
 
 
 
 
 
 
 3 
0 
 
0 
-6 
4 
 
0 
-1 
 
 
 
 
 
 
25 
 
 
 
 
 
 
 
 
Sistema triangular superior. 
Da 3ª: X3=-1, 
Da 2ª substituímos X3=-1, X2=-3, 
Da 1ª substituímos X3=-1, X2=-3 → X1=2. 
 
Métodos Numéricos, 2018, Docente: Zacarias Mutombene Page 5 
 
3. Metodo de Jordan 
O método de Jordan é uma outra melhoria do método de Gauss, neste método tenta-se 
eliminar todos os elementos da matriz excepto os da diagonal. A fórmula geral dos 
cálculos é a seguinte: 
 
( ) 
( ) 
 
( ) 
( )
 
( )
 
Onde: 
 
 
 
Exemplo: 
Resolva o seguinte sistema usando o método Jordan (o mesmo sistema do 
exemplo anterior). 
As seguintes tabelas mostram os cálculos: 
[
 
 
 
] Matriz inicial 
[
 
 
 
] 
*
 
 
 
 
 
 
 
 
+ 
[
 
 
 
] ↔{
 
 
 
→{
 
 
 
 
 
Aplicação do método de Jordan: calculando a matriz inversa. 
4. Método de Decomposição LU (Método Cholesley) 
Considere o sistema . se todos os sub-determinantes diagonais são diferentes de 
zero, é possível aplicar o método de decomposição LU: 
Métodos Numéricos, 2018, Docente: Zacarias Mutombene Page 6 
 
 , |
 
 
| , |
 
 
 
| , etc. até . 
Tenta-se decompor a matriz A na forma: 
 
Sendo ( ) a matriz triangular inferior e ( ) a matriz triangular superior. 
L=(
 
 
) U= (
 
 
) 
Assim torna-se ou ( ) . Pondo então . Isto é, 
em vez de resolver directamente o sistema , resolve 2 sistemas triangular: 
1º (L – triangular inferior) 
2º (U– triangular superior) 
O problema mais importante é como se pode decompor a matriz A, ou em outras 
palavras, como se pode encontrar matrizes L e U? 
Exemplo: Resolva o sistema: 
{
 
 
 
 → A=[
 
 
 
] 
As condições postas para determinantes são satisfeitas: 
a11=2≠0 
det |
 
 
|=3≠0 det |
 
 
 
|=7≠0 
 
Portanto é possível decompor a matriz A. 
Pode verificar que, as matrizes: 
L=[
 
 
 ⁄ 
 ⁄ 
] e U=[
 
 ⁄ 
 ⁄
] 
Verificam A=LU. 
Métodos Numéricos, 2018, Docente: Zacarias Mutombene Page 7 
 
Em seguida, resolva o sistema Ly=B, ou 
{
 
 
 
 
 
 
 
→ Y=(
 
 
 
) 
E ultimamente, resolva o sistema Ux=Y: 
{
 
 
 
 
 
 
 
→ X=(
 
 
 
) 
 
Reposta: a solução do sistema é x=(1, 2, 3). 
Nota: o método de decomposição LU não é prática, há que verificar as condições sobre 
determinantes. Além disso, não é fácil calcular as matrizes L e U, e também há 
necessidade de resolver 2 sistemas triangulares. 
 
Métodos Iterativos 
 
1. Método iterativo geral 
Conteúdo: se de uma certa forma, se transforma o sistema AX=B (1) para forma 
equivalente: 
X=GX + H (2) 
Sendo G=(gij) matriz da mesma dimensão de A, H um vector constante e X vector das 
incógnitas. 
Com X0= um vector inicial escolhido por nós, calcula-se sucessivamente: 
Xn+1=GX+H (3) 
Onde X0=0, o vector iterativo n-esimo passo. Se a série dos vectores X0, X1, X2, …, Xn 
converge para o vector X, isto é: 
limXn=X 
Podemos tornar Xk com k suficientemente grande igual ao vector-soluçãodo sistema 
AX=B. 
Métodos Numéricos, 2018, Docente: Zacarias Mutombene Page 8 
 
O conceito de convergência de uma série de vectores é definido através da definição de 
norma de vectores. 
Def1. Chama-se norma do vector X ao número designado por ‖ ‖ de tal modo que: 
1ª ‖ ‖ e ‖ ‖ se e só se X=0 (vector zero). 
2ª ‖ ‖ ‖ ‖ ‖ ‖ 
3º ‖ ‖ ‖ ‖ ‖ ‖ n 
As seguintes normas de vectores são frequentemente utilizadas: 
1ª norma: ‖ ‖ = √∑ 
 
 =√ 
 
 é a mais utilizada. 
2ª norma: ‖ ‖ = max | | 
 
3ª norma: ‖ ‖ =∑ | |
 
 
Pode se demonstrar que as três normas acima referenciadas são equivalentes. 
Def2: O vector X é o limite da série dos vectores X se: 
 
 
 ‖ ‖ 
Se a série dos vectores é definida por Xn+1=GXn+H converge podemos tomar Xk como k 
suficientemente grande com solução do sistema (1) 
Def3: Chama-se norma de matriz A ao número designado por ‖ ‖ de tal modo que: 
1º ‖ ‖ 0 e ‖ ‖ 0 se e só se A=0 (matriz 0) 
2º ‖ ‖ ‖ ‖ ‖ ‖ 
3º ‖ ‖ ‖ ‖ ‖ ‖ 
 
As seguintes normas de matrizes são mais utilizadas: 
1ª norma: ‖ ‖ = √∑ ∑ 
 
 
 
 é a mais utilizada 
2ª norma: ‖ ‖ = max ( |∑ | |
 
 |) 
 𝑖 𝑛 
 𝑖 𝑛 
Métodos Numéricos, 2018, Docente: Zacarias Mutombene Page 9 
 
 
3ª norma: ‖ ‖ = max(|∑ | |
 
 |) 
 
4ª norma: ‖ ‖ = √ Sendo = valor próprio de maior módulo de A. 
O seguinte teorema é a base da convergência do método iterativo. 
Teorema: Para que o processo iterativo Xn+1=GXn+H seja convergente com qualquer X 
inicial e com qualquer H, é necessário e suficiente que uma das normas da matriz G seja 
inferior a 1. 
‖ ‖ 
1.1. Erro do Método Iterativo Geral 
Na aplicação do método iterativo é preciso saber terminar os cálculos de vectores 
Xn+1=GXn+H, no caso seja convergente. 
É frequentemente considerado o seguinte problema: 
Seja convergente o processo iterativo X=GX+H e seja ξ a precisão adequada previamente 
dada. Para obter a solução aproximada com a precisão ξ, é suficiente que a norna: 
‖ ‖ = 
 = 
 
Sendo dois vectores sucessivos. 
 
 
 
 
 
 
 
 
 𝑗 𝑛 
Métodos Numéricos, 2018, Docente: Zacarias Mutombene Page 10 
 
 
1.2. O Algoritimo 
 
B
Transformar AX=B para 
X=GX+H
É convergente esta 
transformação?
Não
Sim
Escolher Vector X inicial
Xantigo ← X₀
Xnovo=GXantigo + H
Xnovo é Solução
||Xnovo – Xantigo|| ≤ ξ
E
sim
não Xantigo ← Xnovo
1
2
3
4
5
7
8
6
 
Métodos Numéricos, 2018, Docente: Zacarias Mutombene Page 11 
 
Explicação 
Passo1. 
Tente fazer uma transformação do sistema AX=B para a forma X=GX+H com base nos 
seus conhecimentos e experiencia matemática. 
Passo2. 
Verificar se a transformação é útil (convergente) usando o critério: qualquer norma de 
||G||<1. Se sim, passa para o passo seguinte (passo 3). Se não, voltar a procurar uma outra 
transformação (voltando ao passo 1). 
Passo3. 
Escolha arbitrariamente o vector inicial X0. 
Passo4. 
Xantigo ← X0: considere que X0 é o primeiro passo iterativo. 
Passo5. 
Calcular um novo passo pela fórmula (pela transformação escolhida) 
Passo6. 
Verificar se os dois vectores sucessivos estão dentro da precisão . Se sim, passa para 
passo 8. Se não, tem que calcular um novo vector. Mas antes disso realiza o passo 7. 
Passo7. 
Uma preparação para calcular um novo vector. 
Passo8. 
Encontra-se o vector aproximado do vector-solução. Imprimir resultado e terminar. 
 
2. Método Jacobi 
O método Jacobi calcula uma transformação convergente para o método iterativo geral. 
Para obter a forma X=GX+B, usam-se os elementos na diagonal da matriz A, mas de 
seguinte fórmula: 
Métodos Numéricos, 2018, Docente: Zacarias Mutombene Page 12 
 
 
( )
 
 
 
(
 
 
 ∑ 
 
 
 
 )
 
 
 
i=1,2,…,n k=0,1,2,… 
Exemplo: 
Usando o método Jacobi resolva o seguinte sistema com =0.01. 
{ 
 
 
 
 
Da 1ª equação deduz-se: 
Da 2ª equação deduz-se: 
Da 3ª equação deduz-se: 
Assim temos o sistema: 
 
 
 
É claro que: 
X = (
 
 
 
)
⏟ 
 G = (
 
 
 
) 
 
Ou X=GX+H. É convergente esta transformação? 
Usando a 1ª norma de G: 
||G|| = 
√∑ ∑ 
 
 
 
 
√ ( ) ( ) ( ) ( ) ( ) ( ) 
 . Logo, é convergente, 
Sendo 𝑥 (
𝑥1
𝑥2
𝑥 
) H = (
 
 
0 8
) 
G 
Métodos Numéricos, 2018, Docente: Zacarias Mutombene Page 13 
 
Escolher arbitrariamente X0, aqui escolhemos X0 = (0,0,0) 
Calculamos sucessivamente os vectores X pela formula Xn+1=GXn+H, até quando se 
verifica que || || 
Neste passo, arranjamos a seguinte tabela. 
 
 = o 1º componente do vector . 
 
 = o 2º componente do vector . 
 
 = o 3º componente do vector . 
Vecto
r 
 
Xn 
 
 
 
 ‖ ‖ 
Terminação 
( √ 
 
 ) 
X0 0 0 0 ------------- False 
X1 1 1.2 0.8 1.75499 False 
X2 0.68000 0.94000 0.58000 0.46733 False 
X3 0.75400 1.01600 0.63800 0.12090 False 
X4 0.73300 0.99700 0.62300 0.03205 False 
X5 0.73830 1.00210 0.62700 0.00837<0.01 True 
X5 é o vector aproximado da solução com erro =0.01. 
Publicação da solução: 
Como =0.01, é necessário arredondar os componentes do vector X com 2 casa decimais: 
Solução X=(0.74±0.01, 1.00±0.01, 0.63±0.01) 
 
3. Notas finais com Método Iterativo 
Nota1. Se o cálculo de um passo iterativo é errado, pode-se continuar os cálculos 
considerando o resultado errado com um novo vector inicial. Esta capacidade dos métodos 
iterativos é chamada de auto-correção. 
 
Nota2. Em caso geral, é difícil encontrar uma transformação convergente. Aqui se da uma 
sugestão: 
Métodos Numéricos, 2018, Docente: Zacarias Mutombene Page 14 
 
De AX=B → com K≠0, KAX=KB → KAX+IX-IX=KB 
(i=Matriz Unitário) ou IX + (KA-I)X = KB ou IX = ( )⏟ X+ ⏟ 
 
Pode se determinar a matriz G e o vector H da seguinte fórmula: 
{
 
 
 
Mas como escolhe o valor de K para que ||G| |> ||I-kA|| < 1. A escolha de k não esta no plano 
desta disciplina. 
 
Capítulo 3: Resolução de Sistemas de Equações 
Algébricas AX = B 
 
 
1. Resolva os seguintes sistemas de equações com os métodos de Crámer e de Gauss 
 
{
 
 
 
 
 
 
 
2. Resolva os seguintes sistemas de equações com o método de Jordan 
 
a) {
 
 
 
 
 
3. Resolva os seguintes sistemas de equações com o método de Gauss com pivô: 
a) {
 
 
 
 
 
4. É possível calcular o determinante do sistema nos métodos Gauss, GaussPivot, Jordan? 
Caso sim, como se pode calcular? 
 
5. Resolva o seguinte sistema de equações com qualquer método: 
 
 G H 
Métodos Numéricos, 2018, Docente: Zacarias Mutombene Page 15 
 
{
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
6. Usando o método Jordan calcular a matriz inversa da matriz : 
 
 (
 
 
 
 
 
 
 
 
) 
 
Sugestão : Cria-se a matriz estendida A|I (sendo I – a matriz unicidade) e aplique as 
transformações do método Jordaná medida que se obtenha a nova matriz I| , na posição da 
matriz ter-se-á a matriz inversa. 
 A I 
 (
 
 
 
 
 
 
 
 
 
 
) 
 
 
7. Calcular as normas da seguinte matriz: 
 
 
 
 
 
 
8. É possível aplicar o método iterativo no caso em que exista só uma norma inferior que 1? 
 
9. Como se pode escolher o vector inicial para um método iterativo convergente? 
 
10. Resolva o seguinte sistema com o método de Jacobi com eps = 0.001 
 {
 
 
 
 
 
11. Ao resolver o sistema dado no exercício 11 com o método iterativo geral, calculando a matriz A 
e o vector H pelas fórmulas: 
G = I – KA 
H = KB K = 0.06390 
Métodos Numéricos, 2018, Docente: Zacarias Mutombene Page 16 
 
Calcule os vectores 0 ( ).