Finite-budget Newton and chord solves with scheduled factorization reuse

Let $m\ge 1$, let $U\subseteq {\mathbb{R}}^m$ be open, and let $G:U\to {\mathbb{R}}^m$ be $C^1$, $z_0\in U$, residual tolerance $\epsilon \ge 0$, correction budget $N\in {\mathbb{N}}_0$, and refresh period $q\in \mathbb{N}$, $q\ge 1$. Use the coordinate Jacobian convention of The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case. Since $G$ is $C^1$, A total derivative computes every directional derivative, and its matrix is the Jacobian identifies this Jacobian with the matrix of $DG(z)$; write it as $J(z)$. Residual and Jacobian evaluations, norm comparisons and domain tests are returning primitives; no bound on their internal cost is specified. In chord mode also supply a terminating exact linear-system backend: on each square Jacobian it reports singularity if the matrix is singular, and otherwise returns a retained factor object, and each solve on that object terminates with the exact unique solution for its right-hand side. Factorization and solve work are charged individually. The output is a last valid iterate $z\in U$, a status, and the actual residual norm $\mathrm{\parallel }G(z){\mathrm{\parallel }}_2$.

In updated-Newton mode, invoke Finite-budget Newton for a square vector residual with $G,z_0,\epsilon ,N$. It recomputes the Jacobian at every correction and returns its stated residual/budget/failure status. Re-evaluate $G$ at the returned iterate to provide the output residual norm. Count each Jacobian assembly, factorization attempt, and linear solve actually performed.

In chord mode, for $k=0,1,\dots ,N$, first evaluate $G(z_k)$ and put $r_k=\mathrm{\parallel }G(z_k){\mathrm{\parallel }}_2$. If $r_k\le \epsilon$, return $(z_k,\mathtt{\text{root}},r_k)$; this status means only that the residual tolerance was met. If $k=N$, return $(z_k,\mathtt{\text{iteration-budget-exhausted}},r_k)$. Otherwise, at $k=0,q,2q,\dots$, refresh by forming $J_k=DG(z_k)$, attempting to factor it, and retaining the factorization until the next scheduled refresh. The factorization backend must either report singularity or return a factor object whose solve operation gives the exact unique solution of $J_{k}s=-G(z_k)$. If it reports singularity, return $(z_k,\mathtt{\text{singular-jacobian}},r_k)$. At each correction obtain $s_k$ by calling the solve operation on that retained factor object with right-hand side $-G(z_k)$; do not refactor or invoke a fresh matrix-only solve. The exact-solve backend contract makes this the mathematical correction in Newton correction for a square vector residual. If the correction $s_k$ has $z_k+s_k\mathrm{\notin }U$, return $(z_k,\mathtt{\text{invalid-trial}},r_k)$; otherwise set $z_{k+1}=z_k+s_k$ and continue. A refresh period $q=1$ updates the Jacobian every correction; $q>1$ is a chord iteration.

Both modes make no claim that a finite budget reaches an exact root or that a small residual is a forward-error bound. Record the number of Jacobian assemblies, factorization attempts, and linear solves actually performed; a dense LU correction uses one forward and one backward triangular solve. Sparse cost depends on the actual stage matrix and factorization backend and is not bounded here.