Source-linked AI summary
A higher order family of iterative methods for approximating inverse and generalized inverse matrices
Alicia Cordero, Bushra Rani, Juan R. Torregrosa
TL;DR
Efficient matrix inverse and generalized-inverse methods matter, but direct methods can be costly for large sparse matrices and iterative schemes may be sensitive to initial approximations. This paper adds a weight function to the Heun method to construct fourth-order matrix schemes and a particular fifth-order member. The authors report stable schemes identified through dynamics and favorable numerical behavior across different matrix sizes.
Problem
Direct methods can be costly for large sparse matrices, and many iterative schemes are sensitive to the choice of initial approximation.
Source: §1 · pp. 1, 3Method
The authors add a suitable weight function to the third-order Heun method to construct a fourth-order matrix family and a particular fifth-order scheme.
Source: §3 · p. 5, §7 · p. 35Results
The family includes fourth-order schemes and a particular fifth-order scheme; numerical experiments report favorable behavior when convergence and stability, or either one, are guaranteed.
Source: §7 · p. 35Takeaways & Limitations
Real-dynamics analysis identifies stable members of the family, and experiments on random matrices of different sizes report favorable behavior under the stated convergence and stability conditions.
Source: §7 · p. 35The dynamical study is restricted to real-valued dynamics and does not consider complex-valued results.
Source: §5 · p. 20
Abstract
from arXiv · showhide
The development of efficient iterative schemes for approximating the inverse and generalized inverse matrices is important in my research fields. To this end, a family of fourth-order matrix iterative schemes for approximating the inverse and generalized inverse matrices is established by incorporating an appropriate weight function into the scalar Heun method. Moreover, a fifth-order matrix iterative scheme is obtained as a particular member of the proposed family. Under suitable conditions, the theoretical order of convergence is determined for the proposed family, whose stable members are identified through dynamical analysis. To assess their performance and verify the consistency of the theoretical results, some numerical tests are performed on matrices of different sizes.
1 Introduction
Iterative methods offer an efficient and flexible alternative for matrix inversion, while generalized inverses address rectangular or singular matrices. The introduction reviews prior schemes and highlights sensitivity to initial approximations as a motivation for studying dynamics.
1 Introduction
- Direct methods can be computationally expensive for large sparse matrices, motivating iterative methods that repeatedly generate solution approximations.The introduction frames these methods as efficient and flexible tools for inverse problems.Source: §1 · p. 1
- Generalized inverses extend the classical inverse to problems involving singular matrices, alongside schemes for standard inverses of nonsingular matrices.The introduction identifies the Moore-Penrose and Drazin inverses as examples.Source: §1 · p. 2
- Prior work spans arbitrary-order families for standard and generalized inverses and schemes whose attraction basins were studied using discrete complex dynamics.Other cited examples include a seventh-order Drazin-inverse scheme [12] and a fourth-order Moore-Penrose method.Source: §1 · pp. 2–3
- Sensitivity to the initial approximation is a limitation of many iterative schemes, motivating interest in their dynamical behavior.Cordero et al. studied stability of a fourth-order family using real dynamics.Source: §1 · p. 3
2 Preliminaries on the iterative schemes and their dynamics
The preliminaries establish convergence-order terminology, describe generalized inverses, and introduce dynamical concepts used to analyze iterative-scheme stability. They also preview the paper’s matrix schemes and analyses.
2 Preliminaries on the iterative schemes and their dynamics
- Convergence order is defined for scalar and matrix iterative schemes, with quadratic and cubic orders given as examples for scalar sequences.The value of q determines convergence speed; q = 2 is quadratic and q = 3 is cubic.Source: §2 · p. 3
- The Moore-Penrose inverse extends the classical inverse to rectangular matrices, while the Drazin inverse is defined for square matrices by conditions involving the matrix index.The Drazin inverse is useful when a matrix is singular or non-invertible.Source: §2 · p. 4
- The dynamics preliminaries define rational operators, fixed and periodic points, stability, critical points, and basins of attraction.The Fatou–Julia theorem states that each periodic orbit’s immediate basin contains at least one critical point.Source: §2 · p. 4
- The paper develops a fourth-order matrix family, analyzes convergence for standard, Moore-Penrose, and Drazin inverses, then studies dynamics and numerical behavior.Source: §2 · p. 5
3 Proposed iterative scheme
The section builds a fourth-order Heun-type family by adding a weight function to the third-order Heun scheme. A suitable choice yields an inverse-free family, while the convergence result depends on conditions on the weight function.
3 Proposed iterative scheme
- The section also introduces Singh et al.’s two-step, third-order class of iterative schemes for an initial guess x0 ∈ R [24].Source: §3 · p. 5
- The weight function raises the Heun scheme’s convergence order without increasing functional evaluations per iteration.The unweighted Heun method is third-order, whereas the new Heun-type scheme is designed to achieve fourth-order convergence.Source: §3 · p. 6
- Under the theorem’s conditions on the weight function, the proposed scalar iterative scheme has fourth-order convergence.The theorem assumes a simple root, sufficient differentiability, and an initial guess close enough to the root.Source: §3 · p. 6
- The scheme’s weight-function conditions are selected to construct an inverse-free matrix iteration; not every weight satisfying the theorem’s conditions achieves this.An appropriate choice of weight function is required for the inverse-free formulation.Source: §3 · p. 7, §3.1 · p. 8
4 Family of Heun-type matrix iterative schemes
The section formulates an inverse-free Heun-type matrix iteration family and analyzes its convergence for standard and generalized inverses. Its members achieve fourth-order convergence, with a particular member achieving fifth-order convergence.
4 Family of Heun-type matrix iterative schemes
- The inverse-free family BR(β) is derived from the scalar Heun-type scheme for approximating inverse matrices.The authors use this family throughout their convergence analysis.Source: §4 · p. 8
4.1 Convergence analysis for standard inverse
- A particular family member converges to the standard inverse with order five, while the stated family result gives order four.The standard-inverse analysis assumes a nonsingular matrix and an initial approximation with ∥I − AX0∥ < 1.Source: §4.1 · p. 9
- Under the stated convergence conditions, the standard-inverse proof shows the residual tends to zero, implying convergence to A^-1.The proof bounds the residual using the initial condition ∥E0∥ < 1.Source: §4.1 · pp. 9–10
4.2 Convergence analysis for generalized inverses
- For rectangular matrices, the iteration converges to the Moore–Penrose inverse with order four, and a particular member achieves order five.The analysis uses an initial approximation X0 = αA*; it also establishes that the four stated identities are preserved by the iteration.Source: §4.2 · p. 13
- The generalized-inverse analysis establishes convergence to the Moore–Penrose and Drazin inverses through separate proofs for each target.For the Moore–Penrose case, the proof establishes fourth-order convergence; for the Drazin case, it derives convergence under its stated setup.Source: §4.2 · pp. 15, 18, 19
- For singular square matrices, the family converges to the Drazin inverse with order four, while a particular member achieves order five.The Drazin analysis chooses X0 = αA^l with l ≥ ind(A), preserving the Drazin-inverse structure of the initial approximation.Source: §4.2 · pp. 15, 16, 19
5 Dynamical analysis of Heun-type matrix fourth-order scheme
This section analyzes the parameter-dependent real-valued dynamics of the fourth-order Heun-type family, examining fixed points, critical points, stability regimes, and basins of attraction. It describes the associated behaviors, including a basin linked to the root x = 1 in stable cases and an attracting strange fixed point in an unstable case.
5.1 Fixed points of Rβ(x)
- x = 1 is fixed for every β, and x = 0 is a strange fixed point; additional strange fixed points occur when the theorem’s parameter conditions yield real roots of q(x).At β = 5125/1024, the reported additional roots are ex1(β) = 0 and ex2(β) = 5.Source: §5.1 · pp. 20–21
5.1.1 Stability of the fixed points
- The strange fixed point x = 0 is attracting in its theorem-defined parameter region, parabolic at β = 5125/1024 and 6585/1024, and repelling for all other real β values.The strange fixed point ex2(β) is superattracting at β ≈ −0.06403, attracting for β ∈ (−0.207, −1.02×10−7), parabolic at β = −0.207 and β = −1.02×10−7, and repelling elsewhere.Source: §5.1.1 · pp. 21–22
5.2 Critical points of Rβ(x)
- x = 1 is critical for every β; the operator has two free critical points in one parameter regime and four for β ≥ 4.83, with critical-point mergers near β ≈ 1.78 and 4.83.At β = 25/16, cr1(β) = 1 and cr2(β) ≈ 2.25; near β ≈ 1.78, cr1 and cr2 coincide, while near β ≈ 4.83, cr2 and cr3 coincide.Source: §5.2 · p. 24
5.3 Parameter lines
- Parameter lines show cr1 converging to x = 1 for β ∈ (−7.21, 1.78] and (3.64, 3.91) ∪ (7.3, 8.7), while cr2 does so approximately on [−0.75, −0.4] ∪ [0, 1.78].For approximately β ∈ [−0.4, 0), cr2 converges to a strange attractor or an attracting periodic orbit.Source: §5.3 · p. 25
- For the Heun-type family of matrix iterative schemes, every free critical point in β ∈ [−0.7448, −0.4376] ∪ [0, 1.78] converges only to the root x = 1.Source: §5.3 · p. 26
5.4 Bifurcation diagrams
- For cr1, a qualitative change near β ≈ 5 switches attraction from ex1(β) to x = 0; outside β ≈ [4.3, 6.43], period-doubling cascades progress toward chaotic dynamics.The reported dense chaotic bands occur near β ∈ [3.95, 4] and β ≳ 6.8; at β = 3.96, trajectories provide numerical evidence of a strange attractor.Source: Figure 12 · p. 27, §5.4 · pp. 27–28
- For cr2, the interval β ∈ ]−0.21, 0[ corresponds to attraction to ex2(β), while a period-doubling cascade leads to chaotic behavior around β ∈ [−0.43, −0.32].At β = −0.40, bounded non-periodic trajectories on smooth invariant curves indicate a strange attractor.Source: Figure 14 · p. 28, §5.4 · pp. 28–29, Figure 15 · p. 29
5.5 Dynamical lines
- Dynamical lines used up to 40 iterations over 400 initial points, color-coded by convergence to the root, divergence, a strange attractor, or an attracting periodic point.The study also reports numerical experiments on random matrices of different sizes to examine the schemes’ numerical behavior.Source: §5.5 · pp. 29–30
- At β = 25, the stable-and-convergent case has one basin associated with root x = 1, while the remaining initial points diverge.The family is both stable and convergent in this parameter region.Source: Figure 16 · p. 30, §5.5 · p. 30
- At β = 1, the stable-but-not-assured-convergent case has a single root basin larger than at β = 25, despite lying outside Theorem 3’s convergence region.The methods nevertheless exhibit satisfactory dynamical behavior in this region.Source: §5.5 · pp. 29–30, Figure 17 · p. 30
- At β = 5.004, the unstable case has basins for both root x = 1 and a strange attracting fixed point, alongside a divergent region.The strange attracting fixed point is represented in green in the dynamical lines.Source: Figure 18 · p. 30, §5.5 · p. 30
6 Numerical Experiments
Numerical experiments evaluated inverse and generalized-inverse schemes using iterate and residual errors, with results supporting the theoretical convergence orders and favorable performance under stated parameter conditions. The experiments also examine cases where convergence or stability is not guaranteed.
Baseline methods
- The numerical results confirmed quadratic convergence for Newton–Schulz and cubic convergence for Homeier.The experiments tracked successive-iterate and residual errors at each iteration.Source: §6 · pp. 30–31
Standard inverse
- For parameter values guaranteeing convergence and stability, residual and iterate errors were low across matrix sizes, with fewer iterations than lower-order schemes and lower CPU time than Newton–Schulz.Iteration counts rose with matrix size.Source: §6 · p. 31
Parameter regimes
- Some family members achieved fourth-order convergence when stability was guaranteed but convergence was not; members with neither guarantee failed to converge and showed increasing errors.The latter behavior occurred within the prescribed iteration limit.Source: §6 · p. 33
Fifth-order scheme
- The particular Heun-type scheme maintained fifth-order convergence, with sufficiently small iterate and residual errors.For the Drazin inverse, the reported computational order was close to six, with favorable errors and no considerable CPU-time difference.Source: §6 · p. 33
Moore–Penrose inverse
- For the Moore–Penrose inverse, the Heun-type schemes produced small residual and iterate errors, satisfied the inverse conditions with high accuracy, and required fewer iterations than lower-order methods.No considerable performance difference was observed across matrix sizes.Source: §6 · p. 34
Drazin inverse
- For the Drazin inverse, the Heun-type scheme attained a computational convergence order close to six, with favorable errors and no considerable CPU-time difference.The reported ACOC results were consistent with the theoretical orders for Newton–Schulz and Homeier.Source: §6 · p. 35
7 Conclusions
The paper develops a fourth-order Heun-type family for inverse and generalized-inverse matrices, with a particular member achieving fifth-order convergence. Dynamical analysis identifies stable schemes, and numerical experiments report favorable behavior under convergence and stability conditions.
Contributions
- A suitable weight function incorporated into the third-order Heun method yields a fourth-order family of root-finding schemes, extended to standard and generalized matrix inverses; one member has fifth-order convergence.The convergence and convergence orders are proved for the standard, Moore–Penrose, and Drazin inverses.Source: §7 · p. 35
Dynamical analysis and experiments
- Real dynamical analysis identifies stable schemes within the family and studies unstable regions using bifurcation diagrams.Numerical experiments on different-sized random matrices report favorable behavior when both convergence and stability, or either one, is guaranteed.Source: §7 · p. 35