Precondicionador separador duplo : uma nova classe de precondicionadores

Maycon Pereira de Souza

Precondicionador separador duplo : uma nova classe de precondicionadores

Maycon Pereira de Souza

Material

TESE

Idioma

Português

Número de chamada

T/UNICAMP So89p

Outros títulos

[Double splitting preconditioner]

Publicação

Campinas, SP : [s.n.], 2024.

Descrição física

1 recurso online (102 p.) : il., digital, arquivo PDF.

Nota geral

Orientador: Aurelio Ribeiro Leite de Oliveira

Nota de dissertação ou tese

Tese (doutorado) - Universidade Estadual de Campinas (UNICAMP), Instituto de Matemática, Estatística e Computação Científica

Resumo Resumo: Neste trabalho propomos uma generalização da ideia dada em (OLIVEIRA, 1997). O autor citado apresenta uma nova abordagem de se precondicionar o sistema aumentado, sistema oriundo da aplicação dos métodos de pontos interiores a um problema de Programação Linear, denominado Precondicionador... Ver mais Resumo: Neste trabalho propomos uma generalização da ideia dada em (OLIVEIRA, 1997). O autor citado apresenta uma nova abordagem de se precondicionar o sistema aumentado, sistema oriundo da aplicação dos métodos de pontos interiores a um problema de Programação Linear, denominado Precondicionador Separador, em que é feita uma separação nos elementos da matriz do primeiro bloco do sistema aumentado, formando dois conjuntos distintos. Foi mostrado também que o Precondicionador Separador funciona muito bem próximo a uma solução do problema de programação linear, característica que é muito bem vista, pois próximo à solução o sistema tende a ser extremamente mal condicionado. Com base na ideia apresentada por (OLIVEIRA, 1997), propomos um precondicionador duplo para o sistema aumentado, acrescentando alguns parâmetros. Dessa forma, surgem novos precondicionadores, que chamamos de Precondicionador Separador Duplo. Conseguimos mostrar que o precondicionador assim construído é uma generalização do Precondicionador Separador proposto por (OLIVEIRA, 1997). Além disso, mostramos que temos uma variedade de escolhas para alguns blocos que compõem o Precondicionador Separador Duplo e que levam à mesma matriz K (primeiro bloco da matriz precondicionada duplamente) que é a chave principal para a e?ciência do método proposto. Através dos parâmetros que fazem parte do Precondicionador Separador Duplo, podemos fazer com que a matriz em questão não tenha autovalores su?cientemente próximos de zero, o que pode prejudicar o desempenho de métodos iterativos. Além do mais, através de escolhas adequadas desses parâmetros, podemos fazer com que a matriz seja muito bem condicionada nas iterações ?nais do método proposto. Conseguimos encontrar funções desses parâmetros que fornecem o número de condição na norma-2, assim pudemos minimizar essas funções e encontrar toda uma família de soluções que produzem o mesmo número de condição entre o Precondicionador Separador Duplo e o Precondicionador Separador. Provamos assim que o Precondicionador Separador é ótimo nesse sentido. Também é demonstrado que o Precondicionador Separador é ótimo para a norma-1 e norma-8 dada a melhor opção de parâmetros para minimizar a norma-2. Conseguimos empiricamente, com a utilização da norma-1 e norma-8, veri?car que o Precondicionador Separador Duplo pode obter um número de condição menor do que o Precondicionador Separador Ver menos

Abstract: In this work we propose a generalization of the idea given in (OLIVEIRA, 1997). The aforementioned author brings a new approach to precondition the augmented system, a system that comes from the application of methods of interiors points in a Linear Programming problem, called Splitting... Ver mais Abstract: In this work we propose a generalization of the idea given in (OLIVEIRA, 1997). The aforementioned author brings a new approach to precondition the augmented system, a system that comes from the application of methods of interiors points in a Linear Programming problem, called Splitting Preconditioner, in which a separation is made in the elements of the matrix of the ?rst block of the augmented system, forming two distinct sets. It was also demonstrated that the Splitting Preconditioner works very well close to a solution to the linear programming problem, a characteristic that is very well regarded, as close to the solution the system tends to be extremely poorly conditioned. Based on the idea presented by (OLIVEIRA, 1997), we propose a double preconditioner for the augmented system, adding some parameters. In this way, it allowed us a greater range of possibilities for new preconditioners, which we call Double Splitting Preconditioner. We were able to show that the preconditioner thus constructed is a generalization of the Splitting Preconditioner proposed by (OLIVEIRA, 1997). Furthermore, we show that we have a variety of choices for some blocks that make up the Double Splitting Preconditioner and that lead to the same matrix K (?rst block of the doubly preconditioned matrix) which is the main key to the e?ciency of the method proposed. Through the parameters that are part of the Double Splitting Preconditioner, we can ensure that the matrix in question does not have eigenvalues close enough to zero, which can harm the performance of the iterative methods. Furthermore, through appropriate choices of these parameters, we can ensure that the matrix is very well conditioned in the ?nal iterations of the proposed method. We were able to ?nd functions of these parameters that give the condition number in the 2-norm, so we were able to minimize these functions and ?nd a whole family of solutions that produce the same condition number between the Double Splitting Preconditioner and the Splitting Preconditioner. We thus prove that the Splitting Preconditioner is optimal in this sense. It is also shown that the Splitting Preconditioner is optimal for 1-norm and 8-norm given the best choice of parameters to minimize 2-norm. We were able to empirically, using the 1-norm and 8-norm, verify that the Double Splitting Preconditioner can obtain a lower condition number than the Splitting Preconditioner Ver menos

Direito de acesso

Aberto

Assuntos

Pré-condicionadores

Programação linear

Métodos de pontos interiores

Autoria

Souza, Maycon Pereira de, 1985-

Oliveira, Aurelio Ribeiro Leite de, 1962- Orientador

Gomes Neto, Francisco de Assis Magalhães, 1964- Avaliador

Casacio, Luciana, 1983- Avaliador

Rodriguez Heredia, Manolo, 1980- Avaliador