A carregar...
Publicação
Algoritmos para solventes de polinómios matriciais
Orientador(es)
Resumo(s)
Os polinómios matriciais têm um papel importante na teoria das equações diferenciais matriciais resultantes de formulações matemáticas cada vez mais exigentes. Precisamente, uma abordagem para o problema de cálculo numérico de soluções de equações diferenciais matriciais é feita através da computação de solventes do polinómio matricial associado P(X) (Lancaster [25], pag. 525). O primeiro trabalho que se conhece neste âmbito está presente em Dennis [9], que deu origem ao desenvolvimento da teoria algébrica dos polinómios matriciais Dennis [10] e [11] e onde são apresentados Algoritmos de cálculo de solventes. Chama-se à atenção do leitor para Dennis [11], pág. 524, onde são de nidos dois métodos iterativos que permitem o cáculo de solventes. O primeiro, citado como método de Traub, permite a computação do solvente dominante, isto é, do solvente cujos valores próprios são maiores, em módulo, do que os valores próprios de qualquer outro solvente. O segundo Algoritmo é uma versão matricial do método de Bernoulli, que consiste basicamente no método da Potência aplicado à matriz companheira de P(X). Após Dennis [11] vários trabalhos consideraram este método (Lancaster [22], Tsai [38], Higham [19], Pereira [34]). O método de Newton clássico também foi adaptado ao contexto dos polinómios matriciais, primeiro à equação quadrática (Davis [5], Kratz [21], Higham [18], Long [26]) e posteriormente para polinómios de grau m qualquer. Recentemente foi também objeto de estudo em Higham [19] e Pereira [33]. Todos os métodos referidos são desenvolvidos com base na álgebra matricial, isto é, com base na equação P(X) = 0n×n em Cn×n. No presente trabalho é desenvolvido um método do ponto xo considerando as entradas do polinómio matricial P(X), reduzindo o problema ao nível escalar tentando com isso evitar os problemas de cálculo derivados da álgebra matricial sobretudo quando estes envolvem a inversa de uma matriz. É também apresentada uma versão vetorial do método de Newton para polinómios matriciais. Na sequência da ideia desenvolvida em (Marcos [27], pág. 357), onde a equação matricial P(X) = 0n×n é trabalhada ao nivel escalar, é também considerado o método de Newton aplicado à equação formada por n×n equações polinomiais. O objetivo é evitar a derivada de Fréchet e a resolução da respetiva equação matricial de Silvester em cada iteração, tal como acontece no método de nido em (Higham [18], pág. 4). De acordo com Dennis [9], pág. 80, se X é um solvente do polinómio matricial P(X) então X um bloco valor próprio da matriz companheira, CV = V X no caso mónico, ou bloco valor próprio do feixe companheiro, C1V = C2V X no caso não mónico. Relativamente a métodos iterativos com aplicação no cálculo de blocos valores próprios, pelo que se conseguiu apurar, existe apenas o método da Potência de nido em (Dennis [9], pág. 83) e aplicado apenas a polinómios mónicos. Assim, é apresentado o Método Newton Vetorial para Blocos Valores Próprios de nido para blocos valores próprios da matriz companheira e posteriormente adaptado ao cálculo de blocos valores próprios do feixe companheiro ou de um feixe genérico (A, B) = λB − A qualquer. Por último generalizou-se esta formulação para o cálculo de feixes próprios, (λB − A)V = W(λY − X). resultando no Método de Newton Vetorial para Feixes Próprios, de nido para um feixe genérico (A, B) = λB − A.
Matrix polynomials play an important role in the theory of matrix di erential equations. An important approach in searching numerical solutions to matrix di erential equation is through the computation of solvents of the associated matrix polynomial P(X) (Lancaster [25], page 525). The rst work we know in numerical analysis dealing with matrix polynomials is in Dennis [9], which gave origin to Dennis [10] and [11] where an algebraic theory was developed and some algorithms were presented. We refer the reader to Dennis [11], page 524, where two iterative methods to nd solvents are de ned. The rst is a generalization of a scalar algorithm and its purpose is the computation of a dominant solvent, that is a solvent with the eigenvalues greater, in modulus, than the eigenvalues of any other solvent. We will refer this as the Traub method. The second algorithm is a matrix version of the Bernoulli's algorithm, which is essentially a block matrix power method applied to a block companion matrix of P(X). Since Dennis [10], several works have considered this method (Lancaster [22], Tsai [38], Higham [19], Pereira [34]). The classical Newton's method also had been generalized to matrix polynomials, rst to the quadratic equation (Davis [5], Kratz [21], Higham [18], Long [26]) and then to a general degree m. Also this method have been studied in the last years by Higham [19] and Pereira [33]. All methods referred above are based in matrix arithmetics, that is, solving the matrix equation P(X) = 0n×n in Cn×n. Here we will develop a xed point method considering the matrix elementwise, so the computations will be carried at the scalar level, our attempt is to avoid the complications of matrix manipulations specially when dealing with the inverse of a matrix. We present here a vectorial version for the Newton's method for matrix polynomials. This follows the approach of (Marcos [27]), which is to treat again a polynomial matrix equation at a scalar level, for these we consider the polynomial equation by n × n scalar multivariate complex polynomials. The goal here is to avoid the use of the Fréchet derivative which in the respective algorithm it is needed to solve a generalized Sylvester equation at each step (see Higham [18], page 4). In Dennis [9], page 80, it is referred that if X is a solvent of P(X) then it is a block eigenvalue of the companion matrix , CV = V X in the monic case, or a block eigenvalue of the companion pencil, C1V = C2V X in the nonmonic case. Another approach in searching numerical solutions to matrix di erential equation is through the eigenvalues and generalized eigenvectors of the companion matrix or pencil. Related to block eigenvalue calculus, as much as we could, we just nd out the block matrix power method (Dennis [9], page 83) and with application only to monic polynomials. It is therefore presented the Vectorial Newton method to block eigenvalue de ned for the monic case, or a block eigenvalue of the companion pencil, in the nonmonic case. Finally we generalize this formulation for calculating eigenpencils, (λB − A)V = W(λY − X). resulting in the Vectorial Newton Method for eigenpencils.
Matrix polynomials play an important role in the theory of matrix di erential equations. An important approach in searching numerical solutions to matrix di erential equation is through the computation of solvents of the associated matrix polynomial P(X) (Lancaster [25], page 525). The rst work we know in numerical analysis dealing with matrix polynomials is in Dennis [9], which gave origin to Dennis [10] and [11] where an algebraic theory was developed and some algorithms were presented. We refer the reader to Dennis [11], page 524, where two iterative methods to nd solvents are de ned. The rst is a generalization of a scalar algorithm and its purpose is the computation of a dominant solvent, that is a solvent with the eigenvalues greater, in modulus, than the eigenvalues of any other solvent. We will refer this as the Traub method. The second algorithm is a matrix version of the Bernoulli's algorithm, which is essentially a block matrix power method applied to a block companion matrix of P(X). Since Dennis [10], several works have considered this method (Lancaster [22], Tsai [38], Higham [19], Pereira [34]). The classical Newton's method also had been generalized to matrix polynomials, rst to the quadratic equation (Davis [5], Kratz [21], Higham [18], Long [26]) and then to a general degree m. Also this method have been studied in the last years by Higham [19] and Pereira [33]. All methods referred above are based in matrix arithmetics, that is, solving the matrix equation P(X) = 0n×n in Cn×n. Here we will develop a xed point method considering the matrix elementwise, so the computations will be carried at the scalar level, our attempt is to avoid the complications of matrix manipulations specially when dealing with the inverse of a matrix. We present here a vectorial version for the Newton's method for matrix polynomials. This follows the approach of (Marcos [27]), which is to treat again a polynomial matrix equation at a scalar level, for these we consider the polynomial equation by n × n scalar multivariate complex polynomials. The goal here is to avoid the use of the Fréchet derivative which in the respective algorithm it is needed to solve a generalized Sylvester equation at each step (see Higham [18], page 4). In Dennis [9], page 80, it is referred that if X is a solvent of P(X) then it is a block eigenvalue of the companion matrix , CV = V X in the monic case, or a block eigenvalue of the companion pencil, C1V = C2V X in the nonmonic case. Another approach in searching numerical solutions to matrix di erential equation is through the eigenvalues and generalized eigenvectors of the companion matrix or pencil. Related to block eigenvalue calculus, as much as we could, we just nd out the block matrix power method (Dennis [9], page 83) and with application only to monic polynomials. It is therefore presented the Vectorial Newton method to block eigenvalue de ned for the monic case, or a block eigenvalue of the companion pencil, in the nonmonic case. Finally we generalize this formulation for calculating eigenpencils, (λB − A)V = W(λY − X). resulting in the Vectorial Newton Method for eigenpencils.
Descrição
Palavras-chave
Polinómio matricial Equações diferenciais matriciais Cálculo de solventes
Contexto Educativo
Citação
Editora
Universidade da Beira Interior