Revista Internacional de Métodos Numéricos para Cálculo y Diseño en Ingeniería. Vol. 11,4, 499-SOS(1995) . .
UM MÉTODO SEMI-ITERATIVO RELATIVO
AO MÉTODO DE RICHARDSON DE GRAU
DOIS APLICADO A SISTEMAS
LINEARES DEFINIDO-POSITIVOS
NEWTON R. SANTOS
Assessoria de Ensino, Pesquisa e Pos-Graduactio
Centro Federal de Educacao Tecnologica de Minas Gerais
Av. Amazonas, 7675) B. Nova Gameleira
CEP 30510-000, B. Horzzonte, MG, Brasil
Desenvolve-se um novo método semi-iterativo (método RFII-SI) com respeito ao método
iterativo de Richardson de grau dois (método RFII). Aplicam-se ambos os métodos A classe
de sistemas algébricos definido-positivos, que inclui os problemas de Ortega e o da equaciio
solvente do método dos elementos finitos.
SUMMARY
A new semi-iterative method (RF 11-SI) related to Richardson's iterative method (RF 11)
is developed. Both methods are applied to positive definite algebraic systems, which include
Ortega problems and the solving equation for the finite element method.
Uma das técnicas eficientes para resoluciio de sistemas algébricos lineares consiste
no emprego da extrapolaciio de Chebyshev. Tal procedimento aplicado ao método de
Richardson do segundo grau (método RFII) conduz ao método semi-iterativo RFII-SI.
Ambos os métodos constroem sequencias de aproximaqoes da solucáo do problema,
através de um algoritmo de recorrencia em tres termos.
A convergencia é garantida, caso a matriz do sistema algébrico seja definida
positiva, o que inclui inúmeras aplicacoes, como, por exemplo, a equaciio solvente
resultante da aplicacáo do método dos elementos finitos a problemas de valor de
contorno.
Atualmente, tem-se procurado, com vantagem, resolver o sistema algébrico
resultante acima através de métodos iterativos. Por conseguinte, torna-se pertinente o
emprego de semi-iteraciio, quando couber o emprego dessa técnica, o que geralmente
Recibido: Enero 1995
OUniversitat Politecnica de Catalunya (España)
ISSN 0213-1315
N.R. SANTOS
leva a algoritmos mais eficientes. A técnica de semi-iteraq5o eficiente requer que
os autovalores da matriz de iteraq50 do método básico, sobre o qual é construído
o procedimento, possua autovalores reais. Tal ocorre, por exemplo, com a matriz
associada ao problema de Ortega.
CLASSES DE PROBLEMAS
Seja o sistema algébrico linear
Ax = b
onde A é nao singular, de ordem N, x o vetor incógnito e b, vetor dos termos conhecidos
com N componentes, cada um.
Seja a classe de (l),onde
A = CRC-'
(2)
onde R é qualquer matriz com espectro conhecido e C uma matriz nao simétrica valendo
tal que
u = [1 1
...
llT
sendo n par, i.e, metade das componentes sao 1 e outra metade -1.
A matriz inversa C-l é calculada por
A classe de matrizes A, similares a R, assim obtidas denomina-se de "Ortega" e o
problema (1) apresentando este tipo de matriz é denominado "problema de Ortega".
Uma matriz dessa classe, assim gerada, será nao simétrica. É possível obter também
matrizes simétricas através do emprego de um conveniente vetor v em (5).
Outra classe de problemas de interesse é dada pela equaqáo solvente resultante da
aplicas50 do método dos elementos finitos a problemas de valor contorno de amplo
emprego nas várias áreas de engenharia.
Cita-se, entre outros exemplos, o caso do problema de difusa0 do calor em regime
transiente, que é regulado pela equaq5o diferencial parcial
onde a é a difusidade térmica do material; t, o tempo e O, a temperatura adimensional
do corpo num ponto de coordenadas genéricas (x, y) e as condiqoes na fronteira r, do
domínio 0, s5o de 3" espécie.
Neste caso, a equacáo solvente é dada por
+
[C]O [K]Q- [F]= O
(8)
sendo 8 a derivada de 8 em relaciio a t . [C]e[K] sao, respectivamente, as matrizes de
condutancia e rigidez e [F],o vetor forca.
A importancia da classe de Problemas de Ortega reside no fato de possuir espectro
que se pode pré-definir, o que é de importancia para a aplicaciio dos métodos semiiterativos, os quais exigem o preso do conhecimento das limitaqóes dos autovalores da
matriz de iteraqiio, associada ao problema ( l ) , oferecendo em contrapartida, via de
regra, convergencia mais rápida.
Por outro lado, geralmente, pouco se sabe sobre o comportamento dos autovalores
da classe de matrizes presentes nas equacóes solventes do m.e.f. Contudo, espera-se que
o desempenho dos métodos seja, em princípio, análogo ao da primeira classe, tendo em
vista que a matriz em (1) será definida positiva.
MÉTODO RFII E RFII-SI
O método RFII aplicado ao problema (1) constrói uma seqüencia de aproximacóes
x ( ~ da
) sua solucáo dada por
e os parametros r , w e p siio a determinar.
A determinacao de w e p é feita de modo a minimizar o raio espectral p(R) da
matriz de ordem 2N abaixo
o
'=
I
[(1w ) l ( w - p ) l + p F
1
isto requer os cálculos
S
=
b-a
2 - (a b)
+
Dois vetores iniciais sáo necessários ao algoritmo (9). Arbitram-se, por exemplo,
x(O) = O(vetor nulo) e x ( l ) = b.
502
N.R. SANTOS
A convergencia desse método é garantida quando aplicado a problemas com matriz
definida positiva, o que inclui os problemas de interesse já citados.
Observa-se que se pode reescrever (9), compactamente, como
Jn+l) = Ru(n)+ h
sendo R dada por (12) e
h o vetor com 2N
(16)
componentes
h = [ O ph]T
e
(17)
vetor dado pelas 2 N componentes
u(n+l) =
[x(n)
x(n+l)]T
(18)
A convergencia decorre do fato de que o raio espectral
1
p ( ~=
) ( w - 1 ) s < 1, visto que 1 < w < 2 vale, pois, A é matriz definida positiva
er<O.
Sejam, agora, as novas notasoes
n
ank~(k)
=
(19)
k=O
n
(n)=
Y2
com a restriqiio
ank =
ankx(k+l)
(20)
k=O
1. Defina também
("1
[y1
V(") =
yp)l~
(21)
Aplicando-se a técnica de extrapolaqiio de Chebyshev aos esquemas (19) e ( 2 0 ) , e
minimizando os parametros a n k , chega-se ao método semi-iterativo dado pela fórmula
de recorrencia
v(n+l) =
'n+l
2 - (c
+ d ) { [ 2 R-
(C
-
+
d)l]v(") 2hJ
+ (1
-
T ~ + ~ ) v ( ~ - ' ) (22)
onde os parametros rn valem
rl=l,
2z2
r2=--2z2 - 1 '
rn+l = ( 1
-~
)
-
l
(23)
e z , o parametro determinado através das limitasoes c e d dos autovalores de R, i.e.,
z =
+
2 - (c d)
d -c
(24)
A convergencia desse novo método, nos casos em estudo, resulta do fato de que as
constantes c e d sao determinadas por
Estes valores de c e d levados
matriz
implica M = R. Donde, p(M) = p ( ~ <) 1
Agora, basta aplicar o Teorema 4.1 de4, p. 64, para se concluir que a convergencia
está garantida.
Experimentos computacionais relativos aos métodos tratados sáo mostrados nas
Tabelas 1 a V adiante. As tabelas contem os números de iteracoes necessárias, para
convergencia, para cada método e diferentes tamanhos de problemas, respeitada uma
tolerancia (precisiio) de
como critério de parada.
Os resultados referem-se ao problema de Ortega. A variedade de experimentos
numéricos decorre de diferentes situacoes do problema envolvendo, por exemplo,
mudanqa do número de condiqáo, P, da matriz, combinacoes de multiplicidades de
autovalores e, finalmente, parametros aproximados no lugar dos exatos que devem ser
usados na fórmula (22).
Observando-se os resultados obtidos, ve-se que se o número de condicáo P for
pequeno entiio ambos os métodos siio adequados (Tabela 1). Entretanto, quando o
número P cresce o método semi-iterativo torna-se superior, quer os parametros sejam
exatos (Tabelas 11 e 111) quer aproximados (Tabelas IV e V). É importante observar
que o número de iteracoes, em geral, náo depende da ordem da matriz, se mantido fixo
o número de condicáo, o que é um resultado bastante significativo, já que para essa
classe de problema, o método desenvolvido se torna sem dúvida competitivo.
N" de Iteraqoes
Ordem da Matriz
Método RFII
Método RFII-SI
Tabela 1. Problema de Ortega-P = 1.5
N.R. SANTOS
Resta observar que para a obtenqao dos resultados computacionais com o fim de
analisar o efetivo desempenho dos métodos, utilizou-se, exaustivamente, do software
SIRINEL4, desenvolvido pelo autor deste trabalho. Para esse fim foi necessária a
implantaqao, no software SIRINEL, de procedimentos novos, relativos ao novo método
RFII-SI proposto, e o de geraqao dos dados relativos ao problema de Ortega.
Contudo restam, ainda, elaborar experimentos comparativos mais conclusivos,
envolvendo, por exemplo, métodos competitivos como o SOR (superliberaqao com
parametro otimizado) e tratamento de dados relativos ao problema de Stefan, o que
deverá ser feito futuramente.
Entretanto, os resultados já obtidos, nas Tabelas IV e V, servem como um indicativo
inicial para esse outro caso, em virtude de lidar com parametros aproximados, o que
pode de certa forma simular o comportamento dos métodos diante desse novo problema,
para os quais normalmente vai-se deparar com a utilizaqao de parametros nao exatos
nos cálculos.
N" de Iteraqóes
Ordem da Matriz N
50
100
200
500
Método RFII
60
84
120
193
Método RFII-SI
28
35
42
56
Tabela 11. Problema de Ortega-P = N
Multiplicidade de
N o de Iteraqoes
Ordem da Matriz
50
50
100
100
200
200
500
500
Autovalores ( m l , m2) Método RFII Método RFII-SI
18
13
(4971)
18
13
(40,101
18
13
(994
18
14
(90,lO)
18
13
(190,l)
(190,lO)
18
14
18
13
(499,l)
(490,lO)
18
14
Tabela 111. Problema de Ortega- Análise da Multiplicidade de Autovalores (P = 5 )
N" de Iteracoes
Ordem da Matriz N
Método RFII
26
27
27
27
50
1O0
200
500
Método RFII-SI
21
21
21
21
Tabela IV. Problema de Ortega-Parametros Aproximados (Ambos parametros 2 %
de erro) P = 10
N" de Iteracoes
Ordem da Matriz N
50
100
200
500
Tabela V.
Método RFII
29
29
29
29
Método RFII-SI
25
25
25
25
Problema de Ortega-(Ambos par. 5 % de erro) P = 10
AGRADECIMENTOS
O autor agradece o financiamento parcial deste trabalho ao CNPq (processo
30.0407184) e A FAMEPIG (processo CEX-840/90).
1. D.J. Evans, N.R. Santos, "Nonstationary iterative methods for stochastic systems", Comp.
Stud. Rep., Vol. 831, Loughborough University of Technology, U.K., (1993).
2. N.R. Santos, J.D. Evans, "Chebyshev semi-iterative solution of stachastic and Ortega
problems based on second degree Richardson method", Int. J. of Comp. Math., Vol.
53, U.K., (1994).
3. N.R. Santos, G.A.C. Franca "Soluciio Eficiente da Equa~iio de Elementos Finitos
para Problemas Parabólicos", Atas do SIMMEC 91 - Simpósio Mineiro de Mecanica
Computacional, pp. 390-397, Belo Horizonte, MG, (1991).
4. N.R. Santos, O.L. Linhares, "Convergence of Chebyshev semi-iterative methods", Journal
of Comp. and Appl. Math. , Vol. 16, pp. 59-68 (1986).
5. N.R. Santos, "SIRINEL - Um Sistema Especialista para ResolucFio de Sistemas Lineares
Algébricos", Atas do VI1 Congresso Latino-Americano Sobre Métodos Computacionais
Para Engenharia, Vol. 111,pp. 1660-1667, (1986).