多变量Newton-Raphson法复杂度咨询及参考文献请求

Great question! Let's break this down clearly, since you're focusing on Newton-Raphson for multilinear n-variable polynomials (where each variable's degree is at most 1, even if the overall polynomial has a higher total degree like your (x_1x_2x_3) example).

Per-Iteration Complexity #

Each Newton-Raphson step for a single n-variable polynomial follows this core formula:
x_{k+1} = x_k - (\nabla^2 f(x_k))^{-1} \nabla f(x_k)
Here's the breakdown of costs for each component:

• Gradient Calculation ((\nabla f)): A multilinear polynomial in n variables has (2^n) total terms (including the constant term). Computing each of the n partial derivatives requires scanning all terms and adjusting those that include the target variable—this takes (O(n \cdot 2^n)) time total.
• Hessian Calculation ((\nabla^2 f)): Since no variable has degree >1, all second partial derivatives with respect to the same variable ((\partial^2 f/\partial x_i^2)) are 0. For cross-partials ((\partial^2 f/\partial x_i \partial x_j) where (i \neq j)), we're left with (n(n-1)/2) non-zero entries, each computed in (O(2^{n-2})) time. Total cost here is (O(n^2 \cdot 2^n)).
• Linear System Solve: To find the update step (\Delta x), we solve (\nabla^2 f(x_k) \Delta x = -\nabla f(x_k)). Using a general method like LU decomposition, this takes (O(n^3)) time.

Combining these, the dominant term is (O(n^2 \cdot 2^n)) per iteration, since (2^n) grows far faster than (n^3) as n increases.

Total Iterations & Overall Complexity #

The number of iterations depends on two key factors:

• Initial Guess Proximity: If your starting point is close enough to a simple root (where (\nabla f(\text{root}) \neq 0)), Newton-Raphson converges quadratically. This means the number of iterations needed to reach a desired precision (\epsilon) is (O(\log(\epsilon^{-1})))—a constant for fixed precision goals.
• Root Type: For multiple roots, convergence slows to linear, but this is an edge case for most practical purposes with multilinear polynomials.

Assuming a good initial guess and simple root, the total complexity to find a root is (O(n^2 \cdot 2^n)) (since the logarithmic iteration count is a constant factor).

Formal References #

Here are two authoritative sources that cover this analysis in depth:

• Numerical Analysis by Richard L. Burden and J. Douglas Faires: This standard textbook includes a rigorous breakdown of multivariable Newton-Raphson, covering per-iteration costs, convergence rates, and linear system solving. Its sections on multivariate optimization and root-finding directly apply to your multilinear polynomial case.
• Multivariate Newton Methods for Polynomial Systems by Andrew J. Sommese and Charles W. Wampler II: This book focuses specifically on polynomial systems (including multilinear ones) and provides formal complexity proofs for Newton-Raphson and related methods. It delves into both theoretical convergence guarantees and practical computational costs.

内容的提问来源于stack exchange，提问作者noam