Fact-checked by Grok 2 weeks ago

Numerical method

Numerical methods, also referred to as numerical analysis, constitute the branch of mathematics and computer science dedicated to the creation, analysis, and implementation of algorithms that provide approximate solutions to continuous mathematical problems for which exact analytical solutions are either impossible or impractical to compute. These algorithms address challenges in areas such as solving systems of linear and nonlinear equations, optimization, function approximation, and the simulation of differential equations, enabling the numerical handling of real-world models derived from physics, engineering, biology, and economics.^[1]^[2]^[3] At the core of numerical methods lies a focus on error analysis, stability, and efficiency, ensuring that approximations remain accurate despite the limitations of finite precision arithmetic in digital computers. Key techniques encompass polynomial interpolation (including Lagrange and Newton forms, as well as splines for piecewise approximations), numerical quadrature (such as Newton-Cotes and Gaussian rules for integration), root-finding algorithms (like bisection, Newton's method, and secant methods), and methods for ordinary differential equations (including Euler's method, Runge-Kutta schemes, and multistep approaches). These tools are designed to discretize continuous problems into computable forms, with convergence properties analyzed to bound truncation and rounding errors.^[2]^[4] The importance of numerical methods extends to their foundational role in scientific computing and computational science and engineering, where they underpin simulations of complex systems, from climate modeling and structural analysis to machine learning algorithms and financial forecasting. By leveraging high-performance computing, these methods transform intractable problems into feasible computations, driving advancements in fields like aerospace engineering, medical imaging, and data science. Their development has been propelled by the need to solve increasingly sophisticated models, with modern implementations often incorporating parallel processing and adaptive strategies to enhance speed and precision.^[2]^[3]^[1] Historically, numerical methods trace their origins to ancient civilizations, including Egyptian techniques documented in the Rhind Papyrus around 1650 BCE and Greek approximations by Archimedes, but they gained systematic momentum with the invention of calculus by Isaac Newton and Gottfried Wilhelm Leibniz in the late 17th century, which introduced differential equations as tools for modeling natural phenomena. Subsequent contributions from Leonhard Euler, Joseph-Louis Lagrange, and Carl Friedrich Gauss refined approximation techniques, while the advent of electronic computers in the mid-20th century revolutionized the field, enabling large-scale applications and the emergence of specialized software libraries. Today, ongoing research emphasizes robust algorithms for emerging challenges like big data and quantum computing.^[1]^[2]

Fundamentals

Definition

Numerical methods are algorithms designed to approximate solutions to mathematical problems that cannot be solved exactly using analytical techniques, relying instead on finite sequences of arithmetic operations performed on a computer.^[5] These methods address problems in continuous mathematics by transforming them into discrete forms amenable to computation, such as replacing integrals with finite sums or derivatives with difference quotients.^[3] In essence, numerical methods provide practical approximations where exact closed-form solutions are infeasible due to the complexity or nonlinearity of the underlying equations.^[6] Unlike analytical methods, which derive exact solutions through symbolic manipulation and yield closed-form expressions valid for all inputs, numerical methods employ iterative processes or discretizations to generate approximate results that improve with refinement, though they are inherently limited by computational precision.^[7] This distinction arises because analytical approaches seek universal truths via exact algebra or calculus, whereas numerical ones prioritize computability for real-world applications where symbolic solutions are unattainable.^[8] Common problems tackled by numerical methods include finding roots of nonlinear equations, optimizing functions over continuous domains, and solving systems of linear equations derived from physical models.^[3] For instance, root-finding approximates locations where a continuous function equals zero, optimization seeks minima or maxima without exhaustive search, and linear systems resolve balances in interconnected variables, all through discrete approximations that enable efficient computation.^[6] The ultimate aim of these methods is convergence, ensuring that as computational resources increase, the approximations reliably approach the true solutions.^[5]

Error Types

In numerical methods, errors inevitably arise due to the approximation of continuous mathematical problems by discrete computations on finite-precision machines. These errors can significantly impact the reliability of results, and understanding their types is essential for assessing accuracy and designing robust algorithms. The primary categories include truncation errors from discretization and round-off errors from arithmetic limitations, with additional considerations for how errors propagate and measures of problem sensitivity. Truncation error originates from the inherent approximations in replacing infinite or continuous processes with finite ones, such as truncating a Taylor series expansion to approximate derivatives or integrals. For example, the forward finite difference formula for the first derivative, f'(x) \approx \frac{f(x+h) - f(x)}{h}, incurs a truncation error bounded by the remainder term \frac{h}{2} \max_{\xi \in [x, x+h]} |f''(\xi)|, which is O(h) as h \to 0.^[9] This error decreases with smaller step sizes h but must be balanced against other error sources. Mitigation often involves higher-order approximations, like central differences, which reduce the error to O(h^2).^[9] Round-off error arises from the finite precision of floating-point arithmetic, where real numbers are represented with a limited number of bits, leading to rounding discrepancies. In the IEEE 754 standard, a floating-point number is expressed as \pm d_1.d_2 \dots d_p \times \beta^e, where \beta is the base (typically 2), p is the precision, and e the exponent; operations like addition or multiplication may require rounding the result to fit this form, introducing relative errors up to machine epsilon \epsilon_m = \beta^{1-p}/2.^[10] For double-precision arithmetic (\beta=2, p=53), \epsilon_m \approx 1.11 \times 10^{-16}, representing the smallest distinguishable relative difference from 1.^[10] These errors are particularly pronounced in operations involving subtraction of nearly equal values, known as catastrophic cancellation.^[10] In iterative processes, such as solving systems of equations or optimization, small initial errors from truncation or round-off can propagate and accumulate across steps, potentially leading to divergence or degraded accuracy. For instance, in methods like Newton-Raphson, perturbations in function evaluations compound through successive iterations, where the error at step k+1 depends on the accumulated inaccuracies from prior approximations.^[11] This propagation is exacerbated in ill-conditioned problems but can be controlled by monitoring convergence tolerances and using error-correcting techniques like compensated summation.^[11] To quantify accuracy, errors are often measured in absolute or relative terms. The absolute error between an approximation \hat{x} and exact value x is | \hat{x} - x |, capturing the direct deviation regardless of scale.^[9] The relative error, \frac{|\hat{x} - x|}{|x|} (for x \neq 0), normalizes this by the true value's magnitude, providing a scale-invariant measure useful for comparing results across different problem sizes; for example, an absolute error of $10^{-3} is negligible for x=10^6 (relative error $10^{-9}) but significant for x=10^{-3} (relative error 1).^[9] A key indicator of a problem's inherent sensitivity to such errors is the condition number, which bounds how perturbations in input amplify in the output. For a nonsingular matrix A and compatible vector norms, the condition number is defined as

\kappa(A) = \|A\| \cdot \|A^{-1}\|,

where \|\cdot\| denotes the norm; values near 1 indicate well-conditioned problems with minimal error magnification, while large \kappa(A) (e.g., exceeding $10^6) signal ill-conditioning, where small input changes can cause large output variations.^[12] This measure helps predict overall error bounds before applying specific algorithms.^[12]

Theoretical Properties

Consistency

In numerical analysis, a method is defined as consistent if the local truncation error, denoted \tau_h, satisfies \tau_h \to 0 as the discretization parameter h \to 0.^[13] This property ensures that the discrete approximation locally mimics the continuous problem as the grid or step size refines. The order of consistency p quantifies this rate, where \tau_h = O(h^p) for p \geq 1, indicating higher-order methods achieve faster error reduction.^[14] For instance, the forward Euler method for solving ordinary differential equations (ODEs) is first-order consistent, with \tau_h = O(h). To derive this, consider the ODE y' = f(t, y) with exact solution y(t). The method approximates y(t_{n+1}) \approx y(t_n) + h f(t_n, y(t_n)). Substituting the exact solution yields the local truncation error via Taylor expansion:

y(t_n + h) = y(t_n) + h y'(t_n) + \frac{h^2}{2} y''(\xi)

for some \xi \in (t_n, t_n + h), so \tau_h = \frac{h^2}{2} y''(\xi) = O(h).^[15] Higher-order methods, such as Runge-Kutta schemes, achieve p > 1 by incorporating additional derivative approximations.^[16] This concept extends to finite difference approximations for derivatives, central to many numerical methods. For the first derivative, the forward difference (f(x+h) - f(x))/h = f'(x) + (h/2) f''(\xi) illustrates O(h) consistency, derived from Taylor expansion around x:

f(x+h) = f(x) + h f'(x) + \frac{h^2}{2} f''(\xi),

yielding \tau_h = (h/2) f''(\xi). Central differences improve to O(h^2)./10%3A_Numerical_Solutions_of_PDEs/10.03%3A_Truncation_Error) Consistency generalizes across problem classes. For ODEs, it applies as shown for explicit schemes, ensuring local accuracy per step. In partial differential equations (PDEs), such as the heat equation, finite difference discretizations require \tau_h \to 0 in both spatial and temporal steps for consistency. For numerical integration (quadrature), rules like the rectangle method have local truncation error O(h^2) per interval, confirming consistency as h \to 0.^[17]^[18] Consistency is a prerequisite for convergence in well-posed problems, per the Lax equivalence theorem.^[19]

Stability

In numerical methods, stability is the property that ensures small perturbations in the input data, such as rounding errors or minor changes in initial conditions, do not produce disproportionately large errors in the output solution. A numerical method is considered stable if the computed solution remains bounded and close to the exact solution under these perturbations, preventing error amplification over iterations or time steps. This concept is central to ensuring the reliability of approximations in computational mathematics.^[20] For finite difference schemes applied to linear partial differential equations (PDEs) on uniform grids, Von Neumann stability analysis provides a key tool to assess this property. The method assumes errors propagate as Fourier modes of the form v_n^j = g^n e^{i \theta j \Delta x}, where g is the amplification factor derived by substituting this form into the discretized scheme. Stability requires that the magnitude of the amplification factor satisfies |g(\theta)| \leq 1 for all wavenumbers \theta, ensuring that error components do not grow exponentially with time steps. This analysis, pioneered by John von Neumann in the 1940s, is particularly effective for constant-coefficient linear problems and reveals conditions on the time step relative to the spatial discretization to avoid instability.^[21] In the context of ordinary differential equation (ODE) solvers, A-stability is a specific stability criterion introduced by Germund Dahlquist for handling stiff systems. A linear multistep method is A-stable if, when applied to the scalar test equation \frac{dy}{dt} = q y with fixed step size h > 0 and complex q satisfying \Re(q) < 0, all numerical solutions tend to zero as the number of steps n \to \infty. The implicit Euler method exemplifies A-stability, as its stability region encompasses the entire left half of the complex plane, allowing larger step sizes for problems with widely varying eigenvalues. In contrast, explicit methods like the forward Euler often fail A-stability, restricting their use to non-stiff problems.^[22] The Lax-Richtmyer equivalence theorem establishes a fundamental link between stability and convergence for linear finite difference approximations to well-posed initial value problems. It states that a consistent scheme converges to the true solution if and only if it is stable, meaning the discrete solution operator remains uniformly bounded in the appropriate norm over any fixed time interval. This theorem underscores that stability is not merely desirable but necessary for reliable convergence in linear settings, providing intuition that without stability, even consistent approximations can diverge due to error accumulation.^[23] Illustrative examples of instability arise in explicit methods applied to stiff ODEs, where the system's eigenvalues span a wide range, leading to severe step-size restrictions. For instance, explicit Runge-Kutta methods on non-normal linear systems, such as those with Jacobian matrices exhibiting transient growth via pseudospectra, can require step sizes as small as \Delta t \approx 0.1 to maintain stability, despite eigenvalues suggesting larger steps are feasible; without this, errors amplify dramatically, reaching factors like $10^{43} over short intervals. Such behavior highlights why explicit schemes are prone to instability in stiff contexts, often necessitating implicit alternatives.^[24]

Convergence

In numerical methods, convergence refers to the property that the global error e_h, defined as the difference between the numerical solution and the exact solution at a fixed time or point, approaches zero as the discretization parameter h (such as step size) tends to zero: e_h \to 0 as h \to 0.^[25] This ensures that refining the grid or time step brings the approximation arbitrarily close to the true solution of the continuous problem.^[26] A cornerstone result linking convergence to other properties is the Lax equivalence theorem, which applies to linear finite difference schemes for well-posed initial value problems in Banach spaces. The theorem states that, for a consistent scheme approximating a well-posed linear problem, the scheme is convergent if and only if it is stable.^[27] Formally, if the continuous problem is well-posed (i.e., the solution operator is bounded), and the discrete scheme is consistent (local truncation error tends to zero as h \to 0) and stable (the solution operator is uniformly bounded for small h), then the global error satisfies \| u_h - u \| \leq C h^p for some constant C and order p > 0, where u_h is the numerical solution and u is the exact solution.^[27] A sketch of the proof relies on decomposing the global error into the local truncation error and the error from solving the discrete problem. By the triangle inequality, e_h \leq \tau_h + \| v_h - u_h \|, where \tau_h is the local truncation error (which vanishes by consistency) and v_h is the exact solution restricted to the discrete grid. Stability then bounds \| v_h - u_h \| \leq K \| v_h - u \| for a constant K independent of h, and since \| v_h - u \| \to 0 as h \to 0 for well-posed problems, convergence follows. The converse holds because instability implies unbounded growth that prevents error reduction even with consistency.^[19] The order of convergence quantifies the rate at which e_h \to 0, typically expressed as e_h = O(h^p) for some p > 0, meaning the error decreases proportionally to h^p as h shrinks. For example, the composite trapezoidal rule for numerical integration of a twice-differentiable function over [a, b] with n subintervals (so h = (b-a)/n) achieves second-order convergence, where the error is E = -\frac{(b-a) h^2}{12} f''(\xi) for some \xi \in [a, b], thus |E| \leq \frac{(b-a)^3}{12 n^2} \max |f''| = O(h^2)./7%3A_Integration/7.02%3A_Trapezoidal_Rule_of_Integration) This order arises from the linear interpolation underlying the rule, which matches the function and its first derivative at endpoints but incurs quadratic error from the second derivative./7%3A_Integration/7.02%3A_Trapezoidal_Rule_of_Integration) To verify convergence empirically, especially when exact solutions are unavailable, practitioners compute the error for successively halved h values and plot \log |e_h| versus \log h on a log-log scale. The slope of the resulting line approximates -p, confirming the order; for instance, a slope of -2 indicates second-order convergence.^[28] Such studies are routine in validating methods like finite differences for PDEs.^[29] While consistency alone does not guarantee convergence, examples illustrate failure when stability is absent. The forward-time central-space (FTCS) scheme for the linear advection equation u_t + a u_x = 0 (with a > 0) is first-order consistent in both time and space but unconditionally unstable, as its amplification factor has magnitude exceeding 1 for all Courant numbers, leading to exponential growth of errors and non-convergence regardless of how small h becomes.^[30] This underscores that stability is essential for the joint condition to ensure reliable approximation of the exact solution.^[31]

Classification

Direct Methods

Direct methods in numerical analysis are algorithms that compute solutions to problems, such as solving systems of linear equations Ax = b, in a finite number of arithmetic operations, producing exact results under the assumption of exact (infinite precision) arithmetic.^[32] These methods contrast with iterative approaches by guaranteeing termination after a fixed number of steps without relying on convergence criteria.^[32] They are particularly suited for dense, well-conditioned matrices of moderate size, where the goal is to obtain a precise factorization or solution without approximation. The cornerstone of direct methods for linear systems is Gaussian elimination, a systematic process that reduces the coefficient matrix A to upper triangular form through row operations in the forward elimination phase, followed by back-substitution to solve for the unknowns./01:_Chapters/1.07:_LU_Decomposition_Method_for_Solving_Simultaneous_Linear_Equations) This procedure is equivalent to LU decomposition, where the matrix A is factored as

A = LU,

with L a lower triangular matrix containing unit diagonal entries and multipliers from elimination, and U an upper triangular matrix.^[33] Once decomposed, solving Ax = b involves forward substitution to compute Ly = b and then back-substitution for Ux = y, enabling efficient solutions to multiple right-hand sides.^[34] Direct computation of determinants and matrix inverses also falls under these methods, though they are less commonly used for large systems. The determinant of an n \times n matrix can be found via cofactor expansion along the first row, given by

\det(A) = \sum_{j=1}^n a_{1j} C_{1j},

where C_{1j} = (-1)^{1+j} \det(M_{1j}) is the cofactor and M_{1j} is the minor obtained by deleting row 1 and column j./03:_Determinants_and_Diagonalization/3.01:_The_Cofactor_Expansion) This recursive approach has a time complexity of O(n!), rendering it impractical for matrices larger than about n = 10 due to exponential growth in computations.^[35] Similarly, the inverse is computed as A^{-1} = \adj(A)/\det(A), where the adjugate \adj(A) is the transpose of the cofactor matrix; this method shares the same impracticality for sizable n, as it requires O(n \cdot n!) operations./03:_Determinants_and_Diagonalization/3.01:_The_Cofactor_Expansion) In practice, determinants are more efficiently obtained as the product of the diagonal entries of U from LU decomposition (accounting for pivoting sign changes), and inverses via solving A X = I.^[36] The computational complexity of direct methods like Gaussian elimination for an n \times n system is O(n^3) arithmetic operations, dominated by the elimination phase, which performs approximately \frac{2}{3}n^3 floating-point operations.^[37] To enhance numerical stability and prevent division by small pivots that amplify rounding errors, partial pivoting is incorporated: at each elimination step, rows are interchanged to select the entry with the largest absolute value in the current column as the pivot.^[38] This strategy bounds the growth of intermediate elements, ensuring backward stability in most cases, though full pivoting (row and column swaps) can be used at higher cost for severely ill-conditioned problems.^[36] Despite their exactness in theory, direct methods are limited by finite-precision arithmetic on computers, where rounding errors accumulate and can lead to inaccurate solutions, particularly for ill-conditioned matrices with large condition numbers \kappa(A) = \|A\| \cdot \|A^{-1}\|.^[36] Ill-conditioning implies that small perturbations in A or b cause disproportionately large errors in x, and even stable algorithms like pivoted Gaussian elimination cannot mitigate this inherent sensitivity.^[36] Thus, while direct methods excel for problems where n is small to moderate (e.g., up to a few thousand) and matrices are not pathologically ill-conditioned, they become infeasible for very large or sparse systems due to the cubic scaling and fill-in during factorization.^[36]

Iterative Methods

Iterative methods in numerical analysis refine approximate solutions to equations through successive updates starting from an initial guess, continuing until a predefined tolerance is satisfied. These approaches are essential for handling systems where exact solutions are impractical, such as large sparse matrices. A core framework is fixed-point iteration, which reformulates an equation f(x) = 0 into x = g(x), generating the sequence x_{k+1} = g(x_k) for k = 0, 1, 2, \dots, where x_0 is the initial approximation. If the sequence converges to a fixed point p where g(p) = p, then p solves the original equation.^[39] Convergence of fixed-point iteration relies on the Banach fixed-point theorem, applicable in complete metric spaces. The theorem asserts that if g is a contraction mapping—meaning there exists K < 1 such that the distance d(g(x), g(y)) \leq K \, d(x, y) for all x, y in the domain—then g has a unique fixed point, and the iterates x_{k+1} = g(x_k) converge to it from any starting point, with error bounds like d(x_m, p) \leq \frac{K^m}{1 - K} d(x_0, x_1). In one dimension, for differentiable g, this condition holds if |g'(x)| \leq K < 1 over an interval containing the fixed point.^[40]^[39] For linear systems Ax = b with A strictly diagonally dominant or positive definite, specific iterative schemes like Jacobi and Gauss-Seidel apply the fixed-point paradigm. In the Jacobi method, A = D - (L + U) where D is diagonal, L strictly lower triangular, and U strictly upper triangular; the update is x^{(k)} = D^{-1} (L + U) x^{(k-1)} + D^{-1} b, with iteration matrix T_J = D^{-1} (L + U). The Gauss-Seidel method uses A = (D - L) - U, yielding x^{(k)} = (D - L)^{-1} U x^{(k-1)} + (D - L)^{-1} b, with iteration matrix T_G = (D - L)^{-1} U; it incorporates newly computed components during each iteration, often converging faster than Jacobi for the same systems. Both converge if the spectral radius \rho(T) < 1, where \rho(T) is the maximum absolute eigenvalue of the iteration matrix, ensuring the error e^{(k)} = x^{(k)} - x satisfies \|e^{(k)}\| \to 0 as k \to \infty. For many matrices, such as those from discretized elliptic PDEs, \rho(T_G) = [\rho(T_J)]^2.^[41] To accelerate convergence, successive over-relaxation (SOR) modifies Gauss-Seidel by introducing a relaxation parameter \omega \in (0, 2), computing each component as a weighted average: x_i^{(k+1)} = \omega \tilde{x}_i^{(k+1)} + (1 - \omega) x_i^{(k)}, where \tilde{x}^{(k+1)} is the Gauss-Seidel update. The iteration matrix becomes T_{SOR} = (D - \omega L)^{-1} [ \omega U + (1 - \omega) D ], and for \omega = 1, it reduces to Gauss-Seidel. Optimal \omega > 1 (over-relaxation) minimizes \rho(T_{SOR}), often estimated from \rho(T_J) as \omega_b = \frac{2}{1 + \sqrt{1 - \rho(T_J)^2}}, yielding asymptotically faster reduction in error—up to an order of magnitude for model problems like the Poisson equation on grids.^[42] Iterations cease based on stopping criteria that monitor solution quality without knowing the exact answer. A common choice is the relative residual norm \frac{\| A x^{(k)} - b \|}{\| b \|} < \varepsilon, where \varepsilon is a small tolerance (e.g., $10^{-6} to $10^{-12}, depending on precision needs) and \| \cdot \| is typically the Euclidean or infinity norm; this bounds the relative error in x for well-conditioned systems. Additional checks may include stagnation (minimal change in x^{(k)}) or maximum iterations to prevent infinite loops. These methods excel in large-scale algebraic problems, such as those from discretized PDEs, where direct approaches become prohibitive.^[43]

Applications

Algebraic Equations

Numerical methods for solving algebraic equations address systems of the form Ax = b for linear cases and F(x) = 0 for nonlinear ones, where A is a matrix, b and x are vectors, and F is a vector-valued function. These methods are essential in applications ranging from engineering simulations to optimization problems, enabling approximate solutions when exact analytic forms are unavailable or computationally infeasible. Direct methods provide exact solutions within finite arithmetic precision for well-structured systems, while iterative approaches are preferred for large-scale problems to manage storage and time efficiently. For linear systems, direct methods like LU decomposition factor the coefficient matrix A into a lower triangular matrix L and an upper triangular matrix U such that A = LU, allowing forward and backward substitution to solve for x. This approach is particularly effective for dense matrices of moderate size, as it requires approximately \frac{2}{3}n^3 floating-point operations for an n \times n matrix. Iterative methods, such as the conjugate gradient (CG) method, are suited for large sparse symmetric positive definite systems, generating a sequence of conjugate directions to minimize the quadratic form associated with the system. The CG algorithm converges in at most n steps in exact arithmetic but often fewer for well-conditioned problems. Preconditioning enhances iterative solvers by transforming the system to M^{-1}Ax = M^{-1}b, where M approximates A to cluster eigenvalues and accelerate convergence; incomplete LU factorization is a common choice for sparse M. Nonlinear equations for a single variable, f(x) = 0, can be solved using the bisection method, which repeatedly halves an interval [a, b] containing a root (where f(a)f(b) < 0) to isolate the sign change, ensuring linear convergence with error reduction by a factor of \frac{1}{2} per iteration. For faster convergence, the Newton-Raphson method updates the approximation via

x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)},

achieving quadratic convergence—meaning the error squares at each step—provided the initial guess is sufficiently close to the root and f'(x) \neq 0 near it. For systems of nonlinear equations F(\mathbf{x}) = \mathbf{0}, where \mathbf{x} \in \mathbb{R}^n, Newton's method generalizes to

\mathbf{x}^{k+1} = \mathbf{x}^k - J(\mathbf{x}^k)^{-1} F(\mathbf{x}^k),

with J as the Jacobian matrix of partial derivatives; this also exhibits quadratic convergence locally under suitable smoothness and nonsingularity conditions. In large-scale linear and nonlinear systems, sparsity—arising from banded or structured matrices—is exploited to reduce computational cost; for instance, sparse LU decompositions store only nonzero elements, while iterative methods like preconditioned CG use sparse approximate inverses to maintain efficiency without fill-in. Error propagation in ill-conditioned systems, where the condition number \kappa(A) = \|A\| \|A^{-1}\| is large, can amplify small perturbations in b or rounding errors by up to \kappa(A) times the relative input error. A case study in algebraic equations involves solving polynomial equations p(z) = z^n + a_{n-1}z^{n-1} + \cdots + a_0 = 0 by forming the companion matrix

C = \begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\ -a_0 & -a_1 & -a_2 & \cdots & -a_{n-1} \end{pmatrix},

whose eigenvalues are precisely the roots of p(z); these eigenvalues can then be computed using QR iteration or other eigenvalue solvers, offering a stable numerical alternative to direct root isolation for high-degree polynomials.

Differential Equations

Numerical methods for differential equations encompass techniques to approximate solutions to ordinary differential equations (ODEs) and partial differential equations (PDEs), which model dynamic systems in physics, engineering, and biology. For initial value problems in ODEs of the form y' = f(t, y) with y(t_0) = y_0, single-step methods advance the solution one time step at a time using local information, while multi-step methods leverage previous solution values for higher efficiency. These approaches discretize the continuous time domain, balancing accuracy and computational cost.^[44] Single-step methods, such as the Runge-Kutta family, evaluate the right-hand side function multiple times per step to achieve higher-order accuracy without relying on past steps. The classical fourth-order Runge-Kutta (RK4) method, developed from early contributions by Runge in 1895 and Kutta in 1901, uses four stages to approximate the solution over a step size h:

\begin{align*} k_1 &= h f(t_n, y_n), \\ k_2 &= h f\left(t_n + \frac{h}{2}, y_n + \frac{k_1}{2}\right), \\ k_3 &= h f\left(t_n + \frac{h}{2}, y_n + \frac{k_2}{2}\right), \\ k_4 &= h f(t_n + h, y_n + k_3), \\ y_{n+1} &= y_n + \frac{k_1 + 2k_2 + 2k_3 + k_4}{6}. \end{align*}

This can be represented compactly via the Butcher tableau, a matrix form that generalizes Runge-Kutta methods for arbitrary orders, as formalized by Butcher in the 1960s. RK4 provides local truncation error of order O(h^5), making it widely used for non-stiff problems due to its simplicity and accuracy. Multi-step methods, like the Adams-Bashforth explicit schemes, predict the next value using a polynomial interpolation of past points; for example, the second-order variant is y_{n+1} = y_n + \frac{h}{2} (3f_n - f_{n-1}), offering efficiency for smooth solutions by reducing function evaluations. These originated from Adams' predictor formulas in 1855 and Bashforth's refinements in 1883.^[44]^[45] Stiff ODEs, characterized by widely varying time scales (e.g., chemical kinetics with fast and slow reactions), require implicit methods for stability, as explicit schemes like RK4 demand prohibitively small steps. Backward differentiation formulas (BDFs), introduced by Gear in 1971, are implicit multi-step methods that approximate the derivative using backward differences; the second-order BDF is y_{n+1} - y_n = \frac{h}{2} (3y'_{n+1} - 4y'_n + y'_{n-1}), solved via nonlinear systems at each step. BDFs up to order 5 are A-stable, allowing larger steps for stiff systems while maintaining accuracy.^[46] For PDEs, such as the heat equation u_t = \alpha u_{xx} modeling diffusion, numerical solutions combine time-stepping (e.g., from ODE methods) with spatial discretization. Finite difference methods approximate derivatives on a grid; the forward-time centered-space (FTCS) scheme discretizes time explicitly and space centrally:

\frac{u_j^{n+1} - u_j^n}{\Delta t} = \alpha \frac{u_{j+1}^n - 2u_j^n + u_{j-1}^n}{(\Delta x)^2},

yielding u_j^{n+1} = u_j^n + r (u_{j+1}^n - 2u_j^n + u_{j-1}^n) where r = \alpha \Delta t / (\Delta x)^2. This explicit method is first-order in time and second-order in space but requires r \leq 1/2 for stability. FTCS is foundational for parabolic PDEs, though variants like Crank-Nicolson improve unconditional stability.^[47] Finite element and finite volume methods offer flexibility for complex geometries by dividing the domain into elements or volumes. In the finite element method (FEM), the weak or variational formulation minimizes an energy functional; for the Poisson equation -\nabla^2 u = f, multiply by a test function v and integrate by parts: \int_\Omega \nabla u \cdot \nabla v \, dx = \int_\Omega f v \, dx + \int_{\partial \Omega} g v \, ds, where the solution is approximated as u_h = \sum_i u_i \phi_i over basis functions \phi_i on a mesh. Mesh generation involves triangulating the domain, with adaptive refinement for accuracy near singularities, as detailed in Zienkiewicz's foundational texts starting from 1967. Finite volume methods conserve quantities locally by integrating over control volumes, suitable for hyperbolic PDEs. Boundary conditions are incorporated into discretizations to reflect physical constraints. Dirichlet conditions specify u = g on the boundary, enforced by setting nodal values directly in finite differences or essential constraints in FEM. Neumann conditions prescribe the normal derivative \partial u / \partial n = h, approximated in finite differences via one-sided differences (e.g., (u_1 - u_0)/\Delta x = h at the left boundary) or added as natural boundary terms in the variational form of FEM. These ensure well-posedness and physical fidelity.^[48]

Numerical Integration

Numerical integration, also known as quadrature, approximates the definite integral of a function over an interval by summing weighted function evaluations at specific points. These methods are essential when analytical integration is infeasible, providing reliable estimates for continuous functions with known smoothness properties. Quadrature rules derive from polynomial interpolation, balancing accuracy and computational cost, while stochastic approaches like Monte Carlo handle high-dimensional problems effectively. Error analysis guides the choice of method, often involving bounds based on higher derivatives of the integrand. Newton-Cotes formulas form a family of quadrature rules based on interpolating the integrand with polynomials at equally spaced nodes, named after Isaac Newton and Roger Cotes for their foundational work in the 17th and 18th centuries. The simplest is the trapezoidal rule, which approximates ∫_a^b f(x) dx ≈ \frac{b-a}{2} [f(a) + f(b)], with an error term of -\frac{(b-a)^3}{12} f''(\xi) for some ξ ∈ (a,b), assuming f is twice continuously differentiable. This error scales with the cube of the interval length and the second derivative, making it exact for linear functions. For higher accuracy, Simpson's rule uses three points to fit a quadratic: ∫_a^b f(x) dx ≈ \frac{b-a}{6} [f(a) + 4f(\frac{a+b}{2}) + f(b)], with error -\frac{(b-a)^5}{2880} f^{(4)}(\xi) for some ξ ∈ (a,b), exact for cubics and improving convergence for smoother functions. Composite versions divide the interval into subintervals for practical use over large domains. Gaussian quadrature achieves superior precision by selecting nodes and weights as roots and integrals involving orthogonal polynomials, such as Legendre polynomials on [-1,1], ensuring exactness for polynomials up to degree 2n-1 with only n points. Developed by Carl Friedrich Gauss in 1814, this method outperforms Newton-Cotes for the same number of evaluations by optimally placing nodes to minimize interpolation error. For an n-point rule, the approximation is ∑{i=1}^n w_i f(x_i) ≈ ∫{-1}^1 f(x) dx, where x_i are roots of the nth orthogonal polynomial and w_i = ∫_{-1}^1 l_i(x) dx for Lagrange basis l_i. This yields higher-order accuracy without equally spaced points, ideal for smooth integrands. In multiple dimensions, product rules extend one-dimensional quadrature by tensorizing rules over each variable, such as applying Gaussian quadrature separately to each axis for ∫{[a,b]^d} f(\mathbf{x}) d\mathbf{x} ≈ ∑ \prod w{i_j} f(\mathbf{x}_i), though the evaluation count grows exponentially as O(n^d). For high dimensions where this curse of dimensionality hinders deterministic methods, Monte Carlo integration samples points uniformly from the domain and estimates the integral as the volume times the average function value over N samples, with root-mean-square error O(1/√N) independent of dimension. This probabilistic approach converges slowly but reliably for irregular or high-dimensional regions, as established in foundational Monte Carlo theory. Adaptive quadrature refines the mesh dynamically to meet a prescribed error tolerance, using local error estimators to subdivide intervals where the integrand varies rapidly. Romberg integration, introduced by Werner Romberg in 1955, builds on the trapezoidal rule by applying Richardson extrapolation across successively halved step sizes, forming a table of estimates that eliminates even powers of the step size in the error expansion. The (k,m) entry is computed as R_{k,m} = \frac{4^m R_{k,m-1} - R_{k-1,m-1}}{4^m - 1}, providing higher-order approximations and built-in error estimates from table differences, often achieving near-exponential convergence for analytic functions. Improper integrals, featuring singularities or infinite limits, require specialized handling to ensure convergence. Transformations, such as substitution x = 1/t for singularities at endpoints or exponential mappings for infinite domains, recast the integral into a proper form amenable to standard quadrature. For instance, a singularity at a via f(x) ~ (x-a)^{-\alpha} with 0 < α < 1 can be transformed to remove the pole, preserving accuracy while applying Newton-Cotes or Gaussian rules on the new interval.

Challenges and Advances

Computational Complexity

Computational complexity in numerical methods refers to the resources required in terms of time and space to execute algorithms, often analyzed using big-O notation to describe scalability with problem size. For solving systems of linear equations, direct methods like LU decomposition for dense n × n matrices typically require O(n³) floating-point operations for factorization, making them computationally intensive for large-scale problems.^[49] In contrast, methods leveraging structured data, such as the Fast Fourier Transform (FFT) for convolution or spectral analysis, achieve O(n log n) time complexity, enabling efficient handling of signals with thousands of points. Space complexity also varies significantly between approaches. Direct methods, such as Gaussian elimination or Cholesky factorization, demand O(n²) storage to hold the full matrix and factors, which can exceed memory limits for matrices beyond moderate sizes. Iterative methods, particularly matrix-free variants like the conjugate gradient method, avoid explicit matrix storage by evaluating matrix-vector products on-the-fly, reducing space to O(n) or less, ideal for sparse or implicitly defined operators in large simulations.^[50] Scalability challenges arise in high-dimensional settings, where the curse of dimensionality exponentially increases the number of degrees of freedom; for instance, discretizing a d-dimensional partial differential equation on a grid with m points per dimension yields O(m^d) unknowns, rendering standard methods infeasible for d > 3 without dimensionality reduction. Ill-conditioning further exacerbates this, as the condition number κ(A) of the system matrix influences the number of iterations in methods like conjugate gradient, scaling roughly as O(√κ) for convergence, potentially inflating effective time complexity for poorly conditioned problems from physical systems like fluid dynamics.^[51] Parallel computing addresses these issues through techniques like domain decomposition for partial differential equations, where the computational domain is partitioned across processors, enabling scalable solvers with near-linear speedup for elliptic problems on thousands of cores. GPU acceleration further boosts linear algebra operations, such as dense matrix multiplications or sparse solvers, achieving up to 10-100x speedups over CPU implementations by exploiting massive parallelism in hardware like NVIDIA's CUDA architecture.^[52]^[53] Trade-offs between accuracy and efficiency are central, often resolved via low-rank approximations that compress data while preserving essential structure; for example, randomized singular value decomposition reduces a large matrix to rank-k form in O(n k) time with controllable error, allowing efficient processing of massive datasets in machine learning or imaging at the cost of minor fidelity loss.^[54]

Modern Developments

In high-performance computing, adaptive mesh refinement (AMR) has advanced significantly since the early 2000s, enabling efficient large-scale simulations by dynamically adjusting grid resolution in regions of high interest, such as shock fronts in fluid dynamics. The AMReX framework, developed under the Exascale Computing Project, supports block-structured AMR on modern architectures like GPUs, achieving scalability for simulations exceeding billions of cells while minimizing memory overhead.^[55] Similarly, multigrid methods, particularly algebraic multigrid (AMG), have been optimized for parallel environments, solving elliptic PDEs in finite element models with over 200 million degrees of freedom on distributed systems, reducing iteration counts by leveraging coarse-grid corrections.^[56] Hybrid approaches integrating machine learning with traditional numerical methods have emerged prominently post-2010, with physics-informed neural networks (PINNs) serving as a key example for surrogate modeling. Introduced by Raissi et al., PINNs embed physical laws directly into neural network training via a loss function that minimizes residuals of governing equations, such as PDEs, alongside data-fitting terms, allowing solutions to forward and inverse problems without extensive meshing.^[57] This method has been applied to nonlinear PDEs like the Navier-Stokes equations, offering computational speedups over finite difference solvers in scenarios with sparse data, though challenges remain in ensuring long-term stability for time-dependent problems.^[58] Uncertainty quantification in numerical methods has evolved through enhanced Monte Carlo variants and polynomial chaos expansions (PCE) to handle stochastic inputs in simulations. Quasi-Monte Carlo methods, which use low-discrepancy sequences instead of random sampling, improve convergence rates for high-dimensional integrals in reliability analysis, achieving variance reductions of up to an order of magnitude compared to standard Monte Carlo for smooth integrands.^[59] PCE, formalized in modern form by Xiu and Karniadakis, represents random variables as orthogonal polynomial series, enabling efficient propagation of uncertainties in PDE solutions with fewer evaluations than brute-force sampling, as demonstrated in structural mechanics applications.^[60] Quantum numerical methods represent an emerging frontier, with the Harrow-Hassidim-Lloyd (HHL) algorithm providing exponential speedup for solving sparse linear systems on quantum hardware. Proposed in 2009, HHL uses quantum phase estimation to invert matrices in superposition, conditioning on the solution vector to estimate entries with query complexity logarithmic in system size, outperforming classical methods for matrices with low condition numbers.^[61] Early implementations on noisy intermediate-scale quantum devices have solved toy problems like 2D Poisson equations, though error mitigation remains critical for practical scalability.^[62] Software ecosystems have facilitated reproducible and scalable numerics, with libraries like NumPy and PETSc driving 2025 trends toward GPU acceleration and interoperability. NumPy, foundational for array-based computations in Python, supports vectorized operations essential for prototyping numerical algorithms, while libraries like Numba enable just-in-time compilation for up to 10x performance gains on heterogeneous hardware.^[63] PETSc, a suite for parallel linear algebra and multigrid solvers, enables petascale simulations in fields like climate modeling, incorporating adaptive preconditioners and machine learning interfaces for automated solver tuning. These tools emphasize open-source collaboration, ensuring verifiable results through standardized benchmarks and containerization.

References

[1]
[PDF] NUMERICAL ANALYSIS 1. General Introduction ... - University of Iowa
General Introduction. Numerical analysis is the area of mathematics and computer science that creates, analyzes, and implements algorithms for solving nu-.
[2]
[PDF] Lecture Notes on Numerical Analysis - Virginia Tech
Nick Trefethen defines numerical analysis to be 'the study of algorithms for the problems of continuous math- ematics'.
[3]
1 Introduction – Numerical Methods for Data Science
Numerical methods are algorithms that solve problems of continuous mathematics: finding solutions to systems of linear or nonlinear equations, minimizing or ...
[4]
Topics of Numerical Methods
Numerical methods cover topics such as nonlinear equations, matrix algebra, interpolation, regression, integration, ordinary differential equations, ...Missing: types | Show results with:types
[5]
[PDF] Contents 1. Source of errors 1 1.1. Roundoff error 1 1.2. Truncation ...
There are four major ways in which error is introduced into a computation: • Roundoff error due to inexact computer arithmetic; • Truncation error due to ...Missing: propagation | Show results with:propagation
[6]
[PDF] What every computer scientist should know about floating-point ...
There- fore, the result of a floating-point calcu- lation must often be rounded in order to fit back into its finite representation.
[7]
[PDF] Numerical Optimization
(3) Truncation errors: They occurs when the iterative method is terminated, usually after a convergence criterion is met. (4) Propagation of errors: Once an ...
[8]
Condition Numbers · CS 357 Textbook
The condition number of a square nonsingular matrix A is defined by cond ( A ) = κ ( A ) = ∥ A ∥ ∥ A − 1 ∥ . This is also the condition number associated with ...
[9]
[PDF] AM 213B Prof. Daniele Venturi Consistency of numerical methods ...
Local truncation error and consistency. The local truncation error of a numerical scheme is the error. arising from the scheme when we perform one step forward ...
[10]
7.6 Truncation error, consistency and convergence
7.6.2 Consistency. We say that a the discretization of a differential equation, i.e. the numerical scheme, is consistent with the original differential if the ...
[11]
[PDF] Chapter 6 - Differential Equations-ODE
This is called forward Euler method. Taylor series expansion. We note the Taylor formula: y(x + h) ≈ y(x) ...
[12]
[PDF] 5.10 Stability Consistency and Convergence Definition. A one-step ...
This shows that the method is consistent, and the method is convergent. The local truncation error of modified Euler method is. So by part (iii) of the ...
[13]
[PDF] Numerical Methods for Partial Differential Equations - Seongjai Kim
Dec 11, 2023 · In solving PDEs numerically, the following are essential to consider: • physical laws governing the differential equations (physical understand-.
[14]
[PDF] Numerical Integration - UCSD CSE
is called local truncation error. – Indicates consistency. – Used to estimate next time step size in SPICE. • Global Truncation Error (GTE):. – At time point t.
[15]
[PDF] The Lax Equivalence Theorem
Theorem 4.6 (Lax Equivalence Theorem4). For a consistent finite difference scheme, stability is equivalent to convergence.
[16]
Numerical Stability -- from Wolfram MathWorld
Numerical stability is how input errors affect an algorithm. In a stable algorithm, errors lessen; in an unstable one, they cause larger output errors.Missing: definition | Show results with:definition
[17]
[PDF] Chapter 4. Accuracy, Stability, and Convergence - People
The first is by Fourier or von Neumann analysis, applicable in cases where one is dealing with a regular grid, constant coefficients, and the 2-norm. For ...Missing: original | Show results with:original
[18]
[PDF] A special stability problem for linear multistep methods - Math-Unipd
In this paper we shall investigate a different formulation of this requirement. DEFINITION. A k-step method is called A-stable, if all solutions of (1.2) tend ...Missing: original | Show results with:original
[19]
[PDF] Survey of the stability of linear finite difference equations - fsu/coaps
Applying this to the present case, we see that the set (8) is uniformly bounded, and the approximation is stable. Page 8. 274. P. D. LAX, AND R. D. RICHTMYER.
[20]
[PDF] Stiffness of ODEs - People
Stiff equations are problems for which explicit methods don't work. As soon as one tries to turn these ideas into a mathematical criterion for stiffness ...
[21]
[PDF] Convergence of Numerical Models - UNL Digital Commons
A numerical model is convergent if and only if a sequence of model solutions with increasingly refined solution domains approaches a fixed value.
[22]
[PDF] Convergence, Consistency, and Stability
Definition. A one-step finite difference scheme approximating a partial differential equation is a convergent scheme if for any solution to the partial ...
[23]
[PDF] Survey of the Stability of Linear Finite Difference Equations
Our assumption that is complete with respect to the norm plays an important role in the equivalence theorem of Section 8. 3. The Initial Value Problem. Let A ...Missing: original | Show results with:original
[24]
[PDF] Convergence plots and Big-O notation
Power functions are represented by straight lines in a log-log plot, where the coefficient ! is determined by the slope of the line. "#$% = ' (). Page 8 ...Missing: studies | Show results with:studies
[25]
Session 7: Error convergence of numerical methods - Read the Docs
Oct 30, 2017 · Again, a log-log plot will provide more insights about the order of convergence. The slope is 2, so the method is second order accurate.Missing: empirical studies
[26]
8.1 The advection equation - Numerical Methods for Engineers
and consequently the FTCS-scheme is unconditionally unstable for the advection equation and is thus not a viable scheme. Even a very small value of C will ...
[27]
[PDF] Finite Difference Methods For Advection And Diffusion
For constant diffusion, the FTCS method (Richtmyer and Morton 1967) is given by ... the FTCS method is unstable. 9.7 Numerical Test. A numerical solution is ...
[28]
[PDF] Direct Methods to Systems of Linear Equations (Gauss elimination ...
Direct methods include Gaussian elimination, which uses back substitution, and Gauss-Jordan, which uses deletion of a variable.
[29]
[PDF] Gaussian elimination and LU decomposition - UCSD Math
Gaussian elimination reduces linear equations to triangular form. LU decomposition factorizes the matrix A into lower (L) and upper (U) triangular matrices.
[30]
Direct Methods: LU Decomposition - Engineering at Alberta Courses
LU decomposition decomposes a matrix A into L and U, where L is lower and U is upper triangular. This allows solving the system using forward and backward ...
[31]
Cofactor Expansion Calculator | Matrix Determinant ... - ToolDone
Cofactor expansion has O(n!) time complexity, making it impractical for large matrices (n > 4). For larger systems, use LU decomposition, Gaussian elimination, ...
[32]
https://www.researchpublish.com/upload/book/Direct%2520Methods%2520to%2520Systems-01012022-11.pdf
[33]
[PDF] 5.4 Gaussian Elimination and Its Tri-Diagonal Version
Computational complexity of Gaussian elimination with pivoting remains cubic with respect to the dimension of the system: O(n3) arithmetic operations. Of course ...
[34]
[PDF] Lecture 7 - Gaussian Elimination with Pivoting
Column exchange requires changing the order of the xi. For increased numerical stability, make sure the largest possible pivot element is used. This requires ...
[35]
[PDF] Fixed point iteration - Georgia State University
Fixed point iteration. Page 1. Fixed point iteration. Definition. Let g : R → R, then p is a fixed point of g if g(p) = p.
[36]
[PDF] banach's fixed point theorem and applications
The theorem also gives an iterative process by which we can obtain approximations to the fixed point along with error bounds. Definition 1. A fixed point of a ...
[37]
[PDF] 7.3 The Jacobi and Gauss-Seidel Iterative Methods
The matrix form of Jacobi iterative method is. 𝒙𝒙(𝑘𝑘) = 𝐷𝐷−1(𝐿𝐿 + 𝑈𝑈) ... The Gauss-Seidel Method. For each 𝑘𝑘 ≥ 1, generate the components ...
[38]
[PDF] Lecture 18 Classical Iterative Methods - DSpace@MIT
Nov 14, 2006 · The Successive Overrelaxation Method. • In the Successive overrelaxation method, or SOR, the Gauss-Seidel step is extrapolated a factor : x.
[39]
Stopping Criteria - The Netlib
A stopping criterion determines when to stop iteration, using metrics like residual. A good criterion stops when error is small, no longer decreasing, or time ...
[40]
[PDF] A history of Runge-Kutta methods f ~(z) dz = (x. - x.-l) - People
This paper constitutes a centenary survey of Runge--Kutta methods. It reviews some of the early contributio~ due to Runge, Heun, Kutta and Nystr6m and leads ...
[41]
Linear Multistep Numerical Methods for Ordinary Differential Equations
Oct 28, 2008 · The methods that are included are the Adams-Bashforth Methods, Adams-Moulton Methods, and Backwards Differentiation Formulas. Advantages and ...
[42]
[PDF] NUMERICAL SOLUTION OF ORDINARY DIFFERENTIAL EQUATIONS
This book is an expanded version of supplementary notes that we used for a course on ordinary differential equations for upper-division undergraduate students ...<|separator|>
[43]
[PDF] Finite-Difference Approximations to the Heat Equation
Jan 21, 2004 · Abstract. This article provides a practical overview of numerical solutions to the heat equation using the finite difference method.
[44]
4.2. Finite difference method — Mechanical Engineering Methods
First type, or Dirichlet, boundary conditions specify fixed values of y at the boundaries: y ( 0 ) = a and y ( L ) = b . · Second type, or Neumann, boundary ...
[45]
[PDF] Recursive Approach in Sparse Matrix LU Factorization
This operation has computational complexity of order O(n3) when A is a dense matrix, as compared to O(n2) for the solution phase.
[46]
[PDF] Iterative Methods for Sparse Linear Systems Second Edition
In the six years that passed since the publication of the first edition of this book, iterative methods for linear systems have made good progress in ...
[47]
[1804.03957] The curse of dimensionality for numerical integration ...
Apr 11, 2018 · We prove the curse of dimensionality in the worst case setting for multivariate numerical integration for various classes of smooth functions.
[48]
Complexity of Parallel Implementation of Domain Decomposition ...
We discuss the parallel implementation of preconditioned conjugate gradient (PCG)-based domain decomposition techniques for self-adjoint elliptic partial ...
[49]
https://icl.utk.edu/~luszczek/pubs/sciprog.pdf
[50]
[PDF] Randomized algorithms for low-rank matrix approximation - arXiv
This survey explores modern approaches for computing low-rank approximations of high-dimensional matrices by means of the randomized SVD, randomized subspace ...<|control11|><|separator|>
[51]
Adaptive Mesh Refinement - Exascale Computing Project
The Exascale Computing Project (ECP) created co-design centers such as AMReX to develop algorithms and software components optimized for cutting-edge hardware.
[52]
Applications of Algebraic Multigrid to Large-Scale Finite Element ...
We analyze the performance of our algebraic multigrid (AMG) methods on problems with over 237 million degrees of freedom on IBM SP parallel computers. We ...
[53]
Physics-informed neural networks: A deep learning framework for ...
Feb 1, 2019 · We introduce physics-informed neural networks – neural networks that are trained to solve supervised learning tasks while respecting any given laws of physics.
[54]
Data-driven Solutions of Nonlinear Partial Differential Equations
Nov 28, 2017 · We introduce physics informed neural networks -- neural networks that are trained to solve supervised learning tasks while respecting any given ...
[55]
Comparing Monte Carlo and general polynomial chaos approaches
This paper develops a non-intrusive gPC formulation for congestion determination in LVDS and illustrates its effectiveness compared to the MC methods.
[56]
An accuracy comparison of polynomial chaos type methods for the ...
Mar 21, 2013 · In the current paper we consider numerical methods for the propagation of uncertainties through nonlinear differential equations. The main part ...Missing: variants | Show results with:variants<|separator|>
[57]
[0811.3171] Quantum algorithm for solving linear systems of equations
Nov 19, 2008 · Harrow, Avinatan Hassidim, Seth Lloyd. View a PDF of the paper titled Quantum algorithm for solving linear systems of equations, by Aram W.
[58]
Quantum Algorithm for Linear Systems of Equations | Phys. Rev. Lett.
A quantum algorithm that uses the solution to a set of linear equations provides an exponential speedup by comparison with classical alternatives.