Resumen La resolución de ecuaciones y sistemas de ecuaciones no lineales figura entre los problemas más importantes, tanto desde un punto de vista teórico como práctico, de las matemáticas aplicadas, así como también de muchas ramas de las ciencias, la ingeniería, la física, la informática, la astronomía, las finanzas,.... Un vistazo a la bibliografía y la lista de grandes matemáticos que han trabajado en este tema pone de manifiesto un alto nivel de interés contemporáneo en el mismo. Aunque el rápido desarrollo de las computadoras digitales llevó a la aplicación efectiva de muchos métodos numéricos, en la realización práctica, es necesario analizar diferentes problemas tales como la eficiencia computacional basado en el tiempo usado por el procesador, el diseño de métodos iterativos que posean una rápida convergencia a la solución deseada, el control de errores de redondeo, la información sobre las cotas de error de la solución aproximada obtenida, las condiciones iniciales que garanticen una convergencia segura, etc. Dichos problemas constituyen el punto de partida de este trabajo. El objetivo general de esta memoria es diseñar métodos iterativos eficientes para resolver una ecuación o un sistema de ecuaciones no lineales. El esquema más conocido para resolver ecuaciones no lineales es el método de Newton, su generalización a sistemas de ecuaciones fue propuesta por Ostrowski.. En los últimos años, como muestra la amplia bibliografía, ha aumentado de manera considerable la construcción de métodos iterativos, tanto de un paso como multipaso, con el fin de conseguir una convergencia de orden óptimo así como una mejor eficiencia computacional. En general, en esta memoria hemos utilizado la técnica de funciones peso para diseñar métodos de resolución de ecuaciones y sistemas, tanto libres de derivadas como apareciendo éstas en su expresión iterativa. En el Capítulo 2 introducimos los conceptos previos que sustentan el desarrollo de los distintos temas. Entre ellos, cabe destacar los relacionados con los métodos iterativos de resolución de problemas no lineales, en una y varias variables; el concepto de método óptimo (basado en la conjetura de Kung y Traub); las técnicas de demostración empleadas para probar el orden de convergencia local, así como también el operador diferencias divididas [x,y;F], y los conceptos básicos de la dinámica compleja de funciones racionales que utilizaremos para analizar el comportamiento dinámico del operador asociado a cualquier método iterativo. En los Capítulos 3 y 4 hemos desarrollado métodos iterativos óptimos de órdenes 4 y 8, con y sin derivadas, para la resolución de ecuaciones no lineales. En ambos capítulos comenzamos refiriéndonos al estado del arte, para mostrar a continuación los nuevos métodos diseñados, que incluyen familias conocidas pero también nuevos esquemas iterativos, posteriormente continuamos con el análisis de la convergencia de dichas clases de métodos, estableciendo algunos casos particulares, que son analizados en detalle y finalizamos con las pruebas numéricas relacionadas con los esquemas iterativos propuestos. Específicamente, en el Capítulo 3, se presentan los resultados obtenidos al modificar el método clásico de Gauss para la determinación de órbitas preliminares, de manera que incluya en su proceso esquemas iterativos de alto orden de convergencia. Por su parte, en el Capítulo 4 se muestran las propiedades dinámicas de algunos de los esquemas iterativos diseñados de orden 8, así como sus propiedades de estabilidad que son verificadas sobre diferentes funciones test. En el Capítulo 5, presentamos métodos iterativos óptimos de alto orden, con operador derivada, para resolver ecuaciones no lineales. Tras el diseño de estos métodos y el análisis de su convergencia, se transforma dicha clase de esquemas iterativos en otra libre de derivadas, manteniendo su optimalidad. Finalmente, se muestran los resultados de algunas pruebas numéricas, que incluyen la determinación de órbitas preliminares de satélites. El comportamiento dinámico del operador asociado a un método iterativo al ser aplicado sobre la función no lineal a resolver nos proporciona importante información acerca de la estabilidad y fiabilidad de éste. El análisis dinámico de un método iterativo se centra en el estudio del comportamiento asintótico de los puntos fijos (raíces, o no, de la ecuación) del operador, así como en las cuencas de atracción asociadas a los mismos. En el caso de familias paramétricas de métodos iterativos, el análisis de los puntos críticos libres nos permite seleccionar los miembros más estables de dichas familias. El análisis de la dinámica compleja de los métodos diseñados para ecuaciones no lineales se lleva a cabo en el Capítulo 6, donde nos centramos en una de las familias de métodos óptimos presentada en capítulos anteriores. Así, una vez establecido el teorema del escalado, analizamos el comportamiento del operador racional asociado al método actuando sobre polinomios cuadráticos, calculando sus puntos fijos y críticos y analizando su estabilidad. Mostramos los planos de parámetros de los diferentes puntos críticos libres y estudiamos algunos casos particulares mediante planos dinámicos concretos en los que significamos algunas cuencas de atracción que no corresponden a las raíces. A continuación, en el Capítulo 7 se extienden a sistemas las técnicas iterativas diseñadas en el caso escalar, si bien ahora utilizamos funciones peso matriciales. Así construimos métodos de cualquier orden añadiendo sucesivos pasos con la misma estructura. Finalmente, se utiliza el operador diferencias divididas para extender al caso multivariable algunos esquemas iterativos que, a priori, no pueden ser extendidos de forma directa. Todos estos métodos forman parte del estudio numérico que se presenta al final del capítulo, en el que se confirman los resultados teóricos. Esta memoria termina con un capítulo dedicado a problemas abiertos y a líneas futuras de trabajo. Algunos de estos problemas han surgido como consecuencia de los avances obtenidos. / Artidiello Moreno, SDJ. (2014). DISEÑO, IMPLEMENTACIÓN Y CONVERGENCIA DE MÉTODOS ITERATIVOS PARA RESOLVER ECUACIONES Y SISTEMAS NO LINEALES UTILIZANDO FUNCIONES PESO [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/44230

Since the appearance of Newton-Rapshon's method more than 300 years ago, iterative methods have become almost unassailable in most branches of science. The development of computing has made it possible to solve problems of increasing complexity, and this has been accompanied by the need for more efficient and reliable methods. Several tools of discrete dynamics can be used to perform a dynamic analysis of methods and families of iterative methods for solving equations and nonlinear systems, with the aim of extracting information about their stability and classifying them. In this memory a biparametric family of iterative methods is designed that contains the schemes of Ostrowski and Chun as particular cases. The convergence of the family is analyzed and extended to make it suitable for the resolution of systems of nonlinear equations. Dynamic tools are used and developed to carry out a scalar and multivariate study, and problems are solved applied to verify the results of the dynamic study. Finally, the semilocal convergence in Banach spaces of the Chun method is determined. Chapter 2 sets out the basic concepts from which the rest of the chapters will be developed. The Newton method and its derivative free version, the Steffensen method, are transferred to the multivariable case, and the tools of complex and real dynamics are applied to them. In the Chapter 3 a dynamic study of King's family of iterative methods is performed for the resolution of nonlinear equations. The family is applied on a generic quadratic polynomial, and members with a more stable behavior are selected. In the Chapter 4 a biparametric family of iterative methods is designed combining the methods of Ostrowski and Chun and an extension of the family to the multivariable case is done by the use of the operator divided differences. Numerical tests are performed on academic problems and applied to confirm the theoretical results. In the Chapter 5 a dynamic study of the Ostrowski-Chun biparametric family is made and the most stable members are applied to the solution of the Bratu equation, whereas in Chapter 6 a real dynamic study of the family is made in the multivariable case, and in this case the most stable members apply to the resolution of Fischer's equation. In the Chapter 7 the semilocal convergence of the well-known method of Chun, member of the Ostrowski-Chun family, is proved, and the results obtained in the resolution of an integral Hammerstein-type equation are proved. Finally, conclusions and open lines of research are presented. / Desde la aparición del método de Newton-Rapshon hace más de 300 años los métodos iterativos se han hecho poco menos que imprescindibles en la mayoría de las ramas de la ciencia. El desarrollo de la computación ha permitido resolver problemas de complejidad cada vez mayor, y este hecho ha venido acompañado de la necesidad de disponer de métodos más eficientes y fiables. Varias herramientas de la dinámica discreta se pueden utilizar para realizar un análisis dinámico de métodos y familias de métodos iterativos para la resolución de ecuaciones y sistemas no lineales, con el objetivo de extraer información sobre su estabilidad y clasificarlos. En esta Tesis Doctoral se diseña una familia biparamétrica de métodos iterativos que contiene los esquemas de Ostrowski y Chun como casos particulares. Se analiza la convergencia de la familia y se extiende para hacerla apta para la resolución de sistemas de ecuaciones no lineales. Se utilizan y desarrollan herramientas dinámicas para llevar a cabo un estudio escalar y multivariable, y se resuelven problemas aplicados para comprobar los resultados del estudio dinámico. Finalmente, se determina la convergencia semilocal en espacios de Banach del método de Chun. En el Capítulo 2 se exponen los conceptos básicos a partir de los cuales se van a desarrollar el resto de capítulos. Se transfieren al caso multivariable el método de Newton y su versión libre de derivada, el método de Steffensen, y se van aplicando sobre ellos las herramientas de la dinámica compleja y de la real. En el Capítulo 3 se realiza un estudio dinámico de la familia de métodos iterativos de King para la resolución de ecuaciones no lineales. Se aplica la familia sobre un polinomio cuadrático genérico, y se seleccionan los miembros que presentan un comportamiento más estable. En el Capítulo 4 se diseña una familia biparamétrica de métodos iterativos combinando los métodos de Ostrowski y Chun y se hace una extensión de la familia al caso multivariable mediante el uso del operador diferencias divididas. Se realizan pruebas numéricas en problemas académicos y aplicados para confirmar los resultados teóricos. En el Capítulo 5 se hace un estudio dinámico de la familia biparamétrica de Ostrowski-Chun y se aplican los miembros más estables a la solución de la ecuación de Bratu, mientras que en el Capítulo 6 se hace un estudio dinámico real de la familia en el caso multivariable, y en este caso los miembros más estables se aplican a la resolución de la ecuación de Fischer. En el Capítulo 7 se prueba la convergencia semilocal del conocido método de Chun, miembro de la familia de Ostrowski-Chun, y se comprueban los resultados obtenidos en la resolución de una ecuación integral de tipo Hammerstein. Finalmente, se presentan las conclusiones y las líneas abiertas de investigación / Des de l'aparició del mètode de Newton-Rapshon fa més de 300 anys els mètodes iteratius s'han fet poc menys que imprescindibles en la majoria de les branques de la ciència. El desenvolupament de la computació ha permès resoldre problemes de complexitat cada vegada més gran, i aquest fet ha vingut acompanyat de la necessitat de disposar de mètodes més eficients i fiables. Diverses eines de la dinàmica discreta es poden utilitzar per realitzar una anàlisi dinàmica de mètodes i famílies de mètodes iteratius per a la resolució d'equacions i sistemes no lineals, amb l'objectiu d'extreure informació sobre la seva estabilitat i classificar-los. En aquesta tesi doctoral es dissenya una família biparamétrica de mètodes iteratius que conté els esquemes de Ostrowski i Chun com casos particulars. S'analitza la convergència de la família i s'estén per fer-la apta per a la resolució de sistemes d'equacions no lineals. S'utilitzen i desenvolupen eines dinàmiques per dur a terme un estudi escalar i multivariable, i es resolen problemes aplicats per comprovar els resultats de l'estudi dinàmic. Finalment, es determina la convergència semilocal en espais de Banach del mètode de Chun. En el capítol 2 s'exposen els conceptes bàsics a partir dels quals es desenvoluparan la resta de capítols. Es transfereixen al cas multivariable el mètode de Newton i la seva versió lliure de derivada, el mètode de Steffensen, i es van aplicant sobre ells les eines de la dinàmica complexa i de la real. En el capítol 3 es realitza un estudi dinàmic de la família de mètodes iteratius de King per a la resolució d'equacions no lineals. S'aplica la família sobre un polinomi quadràtic genèric, i se seleccionen els membres que presenten un comportament més estable. En el capítol 4 es dissenya una família biparamétrica de mètodes iteratius combinant els mètodes d'Ostrowski i Chun i es fa una extensió de la família al cas multivariable mitjançant l'ús de l'operador diferències dividides. Es realitzen proves numèriques en problemes acadèmics i aplicats per confirmar els resultats teòrics. En el capítol 5 es fa un estudi dinàmic de la família biparamétrica d'Ostrowski-Chun i s'apliquen els membres més estables a la solució de l'equació de Bratu, mentre que en el capítol 6 es fa un estudi dinàmic real de la família en el cas multivariable, i en aquest cas els membres més estables s'apliquen a la resolució de l'equació de Fischer. En el capítol 7 es prova la convergència semilocal del conegut mètode de Chun, membre de la família de Ostrowski-Chun, i es comproven els resultats obtinguts en la resolució d'una equació integral de tipus Hammerstein. Finalment, es presenten les conclusions i les línies obertes d'investigació. / García Maimo, J. (2017). Análisis dinámico y numérico de familias de métodos iterativos para la resolución de ecuaciones no lineales y su extensión a espacios de Banach [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/91483

Este trabalho apresenta a aplicação de técnicas de processamento paralelo na resolução de equações algébricas oriundas do Método de Elementos Finitos aplicado ao Eletromagnetismo, nos regimes estático e harmônico. As técnicas de programação paralelas utilizadas foram OpenMP, CUDA e GPUDirect, sendo esta última para as plataformas do tipo Multi-GPU. Os métodos iterativos abordados incluem aqueles do subespaço Krylov: Gradientes Conjugados, Gradientes Biconjugados, Conjugado Residual, Gradientes Biconjugados Estabilizados, Gradientes Conjugados para equações normais (CGNE e CGNR) e Gradientes Conjugados ao Quadrado. Todas as implementações fizeram uso das bibliotecas CUSP, CUSPARSE e CUBLAS. Para problemas estáticos, os seguintes pré-condicionadores foram adotados, todos eles com implementações paralelizadas e executadas na GPU: Decomposições Incompletas LU e de Cholesky, Multigrid Algébrico, Diagonal e Inversa Aproximada. Para os problemas harmônicos, apenas os dois primeiros pré-condicionadores foram utilizados, porém na sua versão sequencial, com execução na CPU, resultando em uma implementação híbrida CPU-GPU. As ferramentas computacionais desenvolvidas foram testadas na simulação de problemas de aterramento elétrico. No caso do regime harmônico, em que o fenômeno é regido pela Equação de Onda completa com perdas e não homogênea, a formulação adotada foi aquela em dois potenciais, A-V aresta-nodal. Em todas as situações, os aplicativos desenvolvidos para GPU apresentaram speedups apreciáveis, demonstrando a potencialidade dessa tecnologia para a simulação de problemas de larga escala na Engenharia Elétrica, com excelente relação custo-benefício. / This work presents the use of parallel processing techniques in Graphics Processing Units (GPU) for the solution of algebraic equations arising from the Finite Element modeling of electromagnetic phenomena, both in steadystate and time-harmonic regime. The techniques used were parallel programming OpenMP, CUDA and GPUDirect, the latter for those platforms of type Multi-GPU. The iterative methods discussed include those of the Krylov subspace: Conjugate Gradients, Bi-conjugate Gradients, Conjugate Residual, Bi-conjugate Gradients Stabilized, Conjugate Gradients for Normal Equations (CGNE and CGNR) and Conjugate Gradients Squared. All implementations have made use of CUSP, CUSPARSE and CUBLAS libraries. For the static problems, the following pre-conditioners were adopted, all with parallelized implementations and executed on the GPU: Incomplete decompositions, both LU and Cholesky, Algebraic Multigrid, Diagonal and Approximate Inverse. For the time-harmonic varying problems, only the first two pre-conditioners were used, but in their sequential version and running in the CPU, which yielded a hybrid CPU-GPU implementation. The developed computational tools were tested in the simulation of electrical grounding systems. In the case of the harmonic regime, in which the phenomenon is governed by the driven, lossy wave equation, the formulation adopted was that in two potential, the ungauged edge A-V formulation. In all cases, the developed GPU-based tools showed considerable speedups, showing that this is a promising technology for the simulation of large-scale Electrical Engineering problems, with excellent cost-benefit.

Este trabalho apresenta a aplicação de técnicas de processamento paralelo na resolução de equações algébricas oriundas do Método de Elementos Finitos aplicado ao Eletromagnetismo, nos regimes estático e harmônico. As técnicas de programação paralelas utilizadas foram OpenMP, CUDA e GPUDirect, sendo esta última para as plataformas do tipo Multi-GPU. Os métodos iterativos abordados incluem aqueles do subespaço Krylov: Gradientes Conjugados, Gradientes Biconjugados, Conjugado Residual, Gradientes Biconjugados Estabilizados, Gradientes Conjugados para equações normais (CGNE e CGNR) e Gradientes Conjugados ao Quadrado. Todas as implementações fizeram uso das bibliotecas CUSP, CUSPARSE e CUBLAS. Para problemas estáticos, os seguintes pré-condicionadores foram adotados, todos eles com implementações paralelizadas e executadas na GPU: Decomposições Incompletas LU e de Cholesky, Multigrid Algébrico, Diagonal e Inversa Aproximada. Para os problemas harmônicos, apenas os dois primeiros pré-condicionadores foram utilizados, porém na sua versão sequencial, com execução na CPU, resultando em uma implementação híbrida CPU-GPU. As ferramentas computacionais desenvolvidas foram testadas na simulação de problemas de aterramento elétrico. No caso do regime harmônico, em que o fenômeno é regido pela Equação de Onda completa com perdas e não homogênea, a formulação adotada foi aquela em dois potenciais, A-V aresta-nodal. Em todas as situações, os aplicativos desenvolvidos para GPU apresentaram speedups apreciáveis, demonstrando a potencialidade dessa tecnologia para a simulação de problemas de larga escala na Engenharia Elétrica, com excelente relação custo-benefício. / This work presents the use of parallel processing techniques in Graphics Processing Units (GPU) for the solution of algebraic equations arising from the Finite Element modeling of electromagnetic phenomena, both in steadystate and time-harmonic regime. The techniques used were parallel programming OpenMP, CUDA and GPUDirect, the latter for those platforms of type Multi-GPU. The iterative methods discussed include those of the Krylov subspace: Conjugate Gradients, Bi-conjugate Gradients, Conjugate Residual, Bi-conjugate Gradients Stabilized, Conjugate Gradients for Normal Equations (CGNE and CGNR) and Conjugate Gradients Squared. All implementations have made use of CUSP, CUSPARSE and CUBLAS libraries. For the static problems, the following pre-conditioners were adopted, all with parallelized implementations and executed on the GPU: Incomplete decompositions, both LU and Cholesky, Algebraic Multigrid, Diagonal and Approximate Inverse. For the time-harmonic varying problems, only the first two pre-conditioners were used, but in their sequential version and running in the CPU, which yielded a hybrid CPU-GPU implementation. The developed computational tools were tested in the simulation of electrical grounding systems. In the case of the harmonic regime, in which the phenomenon is governed by the driven, lossy wave equation, the formulation adopted was that in two potential, the ungauged edge A-V formulation. In all cases, the developed GPU-based tools showed considerable speedups, showing that this is a promising technology for the simulation of large-scale Electrical Engineering problems, with excellent cost-benefit.

Os métodos incrementais pertencem a uma classe de métodos iterativos que divide o conjunto de dados em subconjuntos ordenados, e que atualiza a imagem ao processar cada subconjunto (sub-iterações). Isso acelera a convergência das reconstruções, e imagens de qualidade são obtidas em menos iterações. No entanto, a cada sub-iteração é necessário calcular os operadores de projeção e retroprojeção, resultando no custo computacional de ordem O(n3) para a reconstrução de imagens de dimensão × . Por outro lado, algumas alternativas baseadas na interpolação em uma grade regular no espaço de Fourier ou em transformadas rápidas não-uniformes, dentre outras ideias, foram desenvolvidas a fim de aliviar esse custo computacional. Além disso, diversas abordagens foram bem sucedidas em acelerar o cálculo das iterações de algoritmos clássicos, mas nenhuma havia sido utilizada em conjunto com os métodos incrementais. Neste trabalho é proposta uma nova abordagem em que a técnica de transformada rápida de Fourier não uniforme (NFFT) é utilizada nas sub-iterações de métodos incrementais com o objetivo de efetuar de forma eficiente os cálculos numericamente mais intensos: a projeção e a retroprojeção, resultando em métodos incrementais com complexidade O(n2 log n ). Os métodos propostos são aplicados à tomografia por radiação síncrotron e os resultados da pesquisa mostram um bom desempenho. / Incremental methods belong to a class of iterative methods that divide the data set into ordered subsets, and which update the image when processing each subset (sub-iterations). It accelerates the reconstruction convergence and quality images are obtained in fewer iterations. However, it is necessary to compute the projection and backprojection operators in each sub-iteration, resulting in the computational cost of O(n3) flops for × images. On the other hand, some alternatives based on interpolation over a regular grid on the Fourier space or on nonequispaced fast transforms, among other ideas, were developed in order to alleviate the computational cost. In addition, several approaches substantially speed up the computation of the iterations of classical algorithms, but the incremental methods had not been benefited from these techniques. In this work, a new approach is proposed in which the nonequispaced fast Fourier transform (NFTT) is used in each subiteration of incremental methods in order to perform the numerically intensive calculations efficiently: the projection and backprojection, resulting in incremental methods with complexity O(n2 log n ). The proposed methods are applied to the synchrotron radiation tomography and the results show a good performance.

Estudamos a otimização do método SOR clássico, para a resolução de um sistema linear Ax = b, com A não-singular, a partir dos resultados de Young [55, 57] e Varga [50, 51] para matrizes de blocos p-cíclicas consistentemente ordenadas. Num primeiro nível, a otimização refere-se à escolha do parâmetro de relaxação do SOR que produz a maior velocidade de convergência, e, num segundo nível, à escolha da p-ciclicidade que apresenta o melhor desempenho com os valores ótimos do parâmetro, e damos ênfase ao caso 2-cíclico. Além disso, descrevemos a otimização do parâmetro em três generalizações: a) num relaxamento das condições sobre o espectro da matriz de Jacobi associada a A; b) no método SOR para matrizes singulares; c) num novo método SOR, que substitui a decomposição A = D - L - U, onde D, L e U são a diagonal de A, a parte triangular inferior estrita de A e a parte triangular superior estrita de A, pela A = D - P - Q, onde P pertence a uma classe de matrizes constru ída a partir das matrizes-escada. Descrevemos também a aplicação do caso singular às cadeias de Markov, comentamos a computação paralela aplicada ao SOR, e apresentamos diversas simulações relativas à otimização desse método. / We study the optimization of the classic SOR method for solving a linear system Ax = b, where A is a nonsingular p-cyclic consistently ordered block matrix, based on the discoveries of Young [55, 57] and Varga [50, 51]. In a first levei, the optimization refers to the choice of the SOR relaxation parameter, which produces the greatest convergence speed and, in a second levei, to the p-cyclicity that presents the best performance with the optimal parameter values and emphasize the 2- cyclic case. Moreover we describe three SOR generalizations concerning optimization: a) by weakening the conditions on the spectrum of Jacobi matrix associated with A; b) by considering the SOR method for singular matrices; c) by approaching a new SOR, that replaces the splitting A = D - L - U, where O, L and U are the diagonal of A, the strict lower triangular part of A and the strict upper triangular part of A. respectively, by this one A = D - P - Q, where P is a stair matrix or a matrix even more general than a stair matrix. We also describe the application of the singular case to Markov chains, discuss parallel computing applied to SOR method, and present severa! simulations regarding the optimization of that method.

CAPES / Este trabalho objetiva apresentar as ideias matemáticas principais da Samambaia de Barnsley, um fractal que recria uma imagem que assemelha-se a uma folha de samambaia da variedade Black Spleenwort e tem como base quatro transformações afins elementares. Algumas mutações da Samambaia de Barnsley são também apresentadas. / This work aims to present the main mathematical ideas of Barnsley’ Fern, a fractal that recreates an image that resembles a fern leaf of the Black Spleenwort variety and is based on four elementary affine transformations. Some mutations of Barnsley’ Fern are also presented.

Estudamos a otimização do método SOR clássico, para a resolução de um sistema linear Ax = b, com A não-singular, a partir dos resultados de Young [55, 57] e Varga [50, 51] para matrizes de blocos p-cíclicas consistentemente ordenadas. Num primeiro nível, a otimização refere-se à escolha do parâmetro de relaxação do SOR que produz a maior velocidade de convergência, e, num segundo nível, à escolha da p-ciclicidade que apresenta o melhor desempenho com os valores ótimos do parâmetro, e damos ênfase ao caso 2-cíclico. Além disso, descrevemos a otimização do parâmetro em três generalizações: a) num relaxamento das condições sobre o espectro da matriz de Jacobi associada a A; b) no método SOR para matrizes singulares; c) num novo método SOR, que substitui a decomposição A = D - L - U, onde D, L e U são a diagonal de A, a parte triangular inferior estrita de A e a parte triangular superior estrita de A, pela A = D - P - Q, onde P pertence a uma classe de matrizes constru ída a partir das matrizes-escada. Descrevemos também a aplicação do caso singular às cadeias de Markov, comentamos a computação paralela aplicada ao SOR, e apresentamos diversas simulações relativas à otimização desse método. / We study the optimization of the classic SOR method for solving a linear system Ax = b, where A is a nonsingular p-cyclic consistently ordered block matrix, based on the discoveries of Young [55, 57] and Varga [50, 51]. In a first levei, the optimization refers to the choice of the SOR relaxation parameter, which produces the greatest convergence speed and, in a second levei, to the p-cyclicity that presents the best performance with the optimal parameter values and emphasize the 2- cyclic case. Moreover we describe three SOR generalizations concerning optimization: a) by weakening the conditions on the spectrum of Jacobi matrix associated with A; b) by considering the SOR method for singular matrices; c) by approaching a new SOR, that replaces the splitting A = D - L - U, where O, L and U are the diagonal of A, the strict lower triangular part of A and the strict upper triangular part of A. respectively, by this one A = D - P - Q, where P is a stair matrix or a matrix even more general than a stair matrix. We also describe the application of the singular case to Markov chains, discuss parallel computing applied to SOR method, and present severa! simulations regarding the optimization of that method.

Os métodos incrementais pertencem a uma classe de métodos iterativos que divide o conjunto de dados em subconjuntos ordenados, e que atualiza a imagem ao processar cada subconjunto (sub-iterações). Isso acelera a convergência das reconstruções, e imagens de qualidade são obtidas em menos iterações. No entanto, a cada sub-iteração é necessário calcular os operadores de projeção e retroprojeção, resultando no custo computacional de ordem O(n3) para a reconstrução de imagens de dimensão × . Por outro lado, algumas alternativas baseadas na interpolação em uma grade regular no espaço de Fourier ou em transformadas rápidas não-uniformes, dentre outras ideias, foram desenvolvidas a fim de aliviar esse custo computacional. Além disso, diversas abordagens foram bem sucedidas em acelerar o cálculo das iterações de algoritmos clássicos, mas nenhuma havia sido utilizada em conjunto com os métodos incrementais. Neste trabalho é proposta uma nova abordagem em que a técnica de transformada rápida de Fourier não uniforme (NFFT) é utilizada nas sub-iterações de métodos incrementais com o objetivo de efetuar de forma eficiente os cálculos numericamente mais intensos: a projeção e a retroprojeção, resultando em métodos incrementais com complexidade O(n2 log n ). Os métodos propostos são aplicados à tomografia por radiação síncrotron e os resultados da pesquisa mostram um bom desempenho. / Incremental methods belong to a class of iterative methods that divide the data set into ordered subsets, and which update the image when processing each subset (sub-iterations). It accelerates the reconstruction convergence and quality images are obtained in fewer iterations. However, it is necessary to compute the projection and backprojection operators in each sub-iteration, resulting in the computational cost of O(n3) flops for × images. On the other hand, some alternatives based on interpolation over a regular grid on the Fourier space or on nonequispaced fast transforms, among other ideas, were developed in order to alleviate the computational cost. In addition, several approaches substantially speed up the computation of the iterations of classical algorithms, but the incremental methods had not been benefited from these techniques. In this work, a new approach is proposed in which the nonequispaced fast Fourier transform (NFTT) is used in each subiteration of incremental methods in order to perform the numerically intensive calculations efficiently: the projection and backprojection, resulting in incremental methods with complexity O(n2 log n ). The proposed methods are applied to the synchrotron radiation tomography and the results show a good performance.

Estudamos a otimização do método SOR clássico, para a resolução de um sistema linear Ax = b, com A não-singular, a partir dos resultados de Young [55, 57] e Varga [50, 51] para matrizes de blocos p-cíclicas consistentemente ordenadas. Num primeiro nível, a otimização refere-se à escolha do parâmetro de relaxação do SOR que produz a maior velocidade de convergência, e, num segundo nível, à escolha da p-ciclicidade que apresenta o melhor desempenho com os valores ótimos do parâmetro, e damos ênfase ao caso 2-cíclico. Além disso, descrevemos a otimização do parâmetro em três generalizações: a) num relaxamento das condições sobre o espectro da matriz de Jacobi associada a A; b) no método SOR para matrizes singulares; c) num novo método SOR, que substitui a decomposição A = D - L - U, onde D, L e U são a diagonal de A, a parte triangular inferior estrita de A e a parte triangular superior estrita de A, pela A = D - P - Q, onde P pertence a uma classe de matrizes constru ída a partir das matrizes-escada. Descrevemos também a aplicação do caso singular às cadeias de Markov, comentamos a computação paralela aplicada ao SOR, e apresentamos diversas simulações relativas à otimização desse método. / We study the optimization of the classic SOR method for solving a linear system Ax = b, where A is a nonsingular p-cyclic consistently ordered block matrix, based on the discoveries of Young [55, 57] and Varga [50, 51]. In a first levei, the optimization refers to the choice of the SOR relaxation parameter, which produces the greatest convergence speed and, in a second levei, to the p-cyclicity that presents the best performance with the optimal parameter values and emphasize the 2- cyclic case. Moreover we describe three SOR generalizations concerning optimization: a) by weakening the conditions on the spectrum of Jacobi matrix associated with A; b) by considering the SOR method for singular matrices; c) by approaching a new SOR, that replaces the splitting A = D - L - U, where O, L and U are the diagonal of A, the strict lower triangular part of A and the strict upper triangular part of A. respectively, by this one A = D - P - Q, where P is a stair matrix or a matrix even more general than a stair matrix. We also describe the application of the singular case to Markov chains, discuss parallel computing applied to SOR method, and present severa! simulations regarding the optimization of that method.