Overview
Lagrange interpolation gives a direct formula for the polynomial through samples, making the role of each point explicit.
CoreSource checked
Lagrange Interpolation
Builds an interpolating polynomial as a weighted sum of basis polynomials.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Numerical Methods
- Difficulty
- Intermediate
- Family
- Interpolation
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
basis polynomialsample weightinterpolating polynomialexact sample fit
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n^2)
Average
O(n^2)
Worst
O(n^2)
Space
O(n)
When to Use
- Use when solving equations needs basis polynomial.
- Use when the input matches the assumptions behind interpolation.
When Not to Use
- Avoid when the problem is ill-conditioned and no scaling or stability checks are available.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Builds an interpolating polynomial as a weighted sum of basis polynomials
- Uses basis polynomial and sample weight to guide the work.
- Produces approximate numeric result.
Use Cases
- Solving equations
- Approximating integrals
- Working with matrices and differential equations
Inputs
- Numeric function, matrix, or sampled data
- Initial estimate or discretization
- Tolerance
Outputs
- Approximate numeric result
- Error estimate or residual
Key Formulas (1)
Lagrange basis
Li(x) = product_{j ≠ i} (x − xj) / (xi − xj)
L_i(x) = product_{j != i} (x - x_j) / (x_i - x_j)Builds interpolation weights from sample locations.
Pseudocode
- 1.Prepare the inputs and state needed for Lagrange Interpolation.
- 2.Apply the basis polynomial step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return approximate numeric result.
Canonical Example
- Input
- Lagrange Interpolation input with a small representative case
- Output
- Approximate numeric result
- Explanation
- Lagrange Interpolation applies basis polynomial to produce approximate numeric result.
Implementation Notes
- Check convergence with residuals or estimated error, not iteration count alone.
- Keep the basis polynomial step separate enough to test independently.
Common Pitfalls
- Ignoring conditioning and residuals can produce plausible-looking but wrong numeric answers.
- Forgetting to check edge cases can make Lagrange Interpolation look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow the numeric approximation improving against the target function, matrix, or state.
Step 1 of 4: Prepare the inputs and state needed for Lagrange Interpolation.
numerical-methods-mechanismNotes
Lagrange Interpolation should be used with the assumptions and tradeoffs of interpolation in mind.
Sources (1)
What each reference supports for this entry.
Numerical Recipes
BookNumerical methods reference covering Lagrange interpolation and interpolation error behavior.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toNewton Interpolation
Newton interpolation uses divided differences instead of Lagrange bases.
Variant ofPolynomial Interpolation
Lagrange interpolation constructs the polynomial from basis functions.
Related Algorithms
Tags
Numerical MethodsInterpolationPolynomialsApproximation