Die Druckversion wird nicht mehr unterstützt und kann Darstellungsfehler aufweisen. Bitte aktualisiere deine Browser-Lesezeichen und verwende stattdessen die Standard-Druckfunktion des Browsers.

Numerical Analysis

Introduction

Numerical analysis studies algorithms for obtaining reliable numerical approximations to mathematical problems. You use it when an exact symbolic solution is unavailable, too expensive, or less useful than a controlled numerical approximation. The subject connects analysis, linear algebra, differential equations, computer science, and scientific computing.

A numerical result is not just a decimal answer. A complete numerical solution also asks: How accurate is the approximation? How sensitive is the problem to small changes in the data? Does the algorithm amplify rounding errors? How much computation and memory are required? How can you verify that the implementation is behaving as theory predicts?

By the end of this aiMOOC, you should be able to select and analyze numerical methods for common university-level problems, estimate and interpret errors, reason about conditioning and stability, implement algorithms responsibly, compare alternatives, and communicate the limitations of computed results.

Why Numerical Analysis Matters

Many models in engineering, physics, economics, data science, and applied mathematics reduce to equations that cannot be solved conveniently by elementary formulas. Numerical methods make these models computationally usable. Typical tasks include finding a root of a nonlinear equation, solving a large linear system, constructing an interpolant from measured data, evaluating an integral, and advancing a differential equation through time.

The discipline is concerned with both mathematics and computation. A mathematically convergent formula can still behave poorly in finite-precision arithmetic, while a practical algorithm may be designed specifically to reduce cancellation, control step size, exploit sparsity, or reuse matrix factorizations.

Foundations: Approximation, Error, and Conditioning

Absolute and Relative Error

Suppose the exact quantity is $x$ and a computed approximation is $\hat{x}$ . The absolute error is

$| x - \hat{x} | .$

When $x \neq 0$ , the relative error is

$\frac{| x - \hat{x} |}{| x |} .$

Relative error is often more informative when values vary greatly in scale. An absolute error of $1 0^{- 4}$ may be negligible for a quantity near $1 0^{3}$ but serious for a quantity near $1 0^{- 5}$ .

Error has several sources. Data error comes from measurement or input uncertainty. Truncation error appears when an infinite or continuous mathematical process is replaced by a finite approximation. Round-off error comes from finite-precision arithmetic. A good analysis separates these sources rather than treating every discrepancy as the same phenomenon.

Floating-Point Arithmetic and Cancellation

Computers usually represent real numbers with a finite number of binary digits. Consequently, many real numbers are stored only approximately. Each arithmetic operation can introduce rounding. These effects are normally tiny, but they can accumulate or become magnified.

A classic danger is catastrophic cancellation: subtracting two nearly equal numbers can destroy significant digits. Algebraically equivalent formulas can therefore have very different numerical behavior. For example, when $x$ is large and positive, evaluating

$\sqrt{x^{2} + 1} - x$

directly can lose accuracy. Multiplying by the conjugate yields the equivalent expression

$\frac{1}{\sqrt{x^{2} + 1} + x},$

which avoids subtracting two nearly equal large quantities.

Conditioning and Stability

Conditioning is a property of the mathematical problem. A well-conditioned problem changes only modestly when the input changes slightly; an ill-conditioned problem may change dramatically. For a nonsingular linear system $A x = b$ , a matrix condition number such as $κ (A)$ helps quantify sensitivity.

Stability is a property of an algorithm. A stable algorithm controls the effect of small computational errors. A stable method cannot remove the inherent sensitivity of an ill-conditioned problem, but it avoids adding unnecessary sensitivity of its own.

This distinction is central: a surprising answer may result from uncertain data, an ill-conditioned model, an unstable algorithm, a programming error, or some combination of these factors.

Convergence and Order

Many numerical methods generate a sequence of approximations $x_{0}, x_{1}, x_{2}, \dots$ that approaches a target $x^{*}$ . If the errors satisfy approximately

$| e_{n + 1} | \approx C | e_{n} |^{p},$

where $e_{n} = x_{n} - x^{*}$ , then $p$ describes the local order of convergence. Larger order can mean rapid error reduction near the solution, but each iteration may also cost more. Practical method choice therefore depends on convergence speed, robustness, derivative requirements, memory, and evaluation cost.

Root Finding for Nonlinear Equations

A root-finding problem seeks $x^{*}$ such that $f (x^{*}) = 0$ . Numerical root finding illustrates several major themes at once: bracketing, iteration, convergence rates, stopping rules, and failure modes.

Bisection Method

If $f$ is continuous on $[a, b]$ and Fehler beim Parsen (Syntaxfehler): {\displaystyle f(a)f(b)<0} , the bisection method repeatedly halves the interval and keeps the subinterval that still brackets a sign change. Its convergence is predictable and robust. After $n$ bisections, the interval width is $(b - a) / 2^{n}$ .

Bisection is usually slower than higher-order open methods, but it provides a valuable reliability benchmark. A practical solver often combines bracketing with a faster method.

Newton's Method and the Secant Method

Newton's method updates an approximation using

$x_{n + 1} = x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})} .$

Near a simple root and under suitable smoothness and starting conditions, Newton's method is locally quadratically convergent. However, a poor initial guess, a small derivative, or an unfavorable function geometry can cause slow progress or divergence.

The secant method replaces the derivative by a finite slope from two recent iterates. It avoids explicit derivative evaluation and is often faster than bisection, but it does not preserve a bracket automatically.

Stopping Criteria and Verification

A solver should not stop merely because an iteration counter has reached an arbitrary value. Useful tests include a small residual $| f (x_{n}) |$ , a small step $| x_{n + 1} - x_{n} |$ , a certified bracket width, or a combination of criteria scaled to the problem. A small residual does not always imply a small forward error when the problem is poorly conditioned, so verification should reflect the mathematical sensitivity of the root.

Interpolation and Approximation

Interpolation constructs a function that matches supplied data values exactly at selected nodes. Approximation more broadly seeks a function that represents data or another function according to a chosen criterion.

Polynomial Interpolation

Given distinct nodes $x_{0}, \dots, x_{n}$ and values $y_{0}, \dots, y_{n}$ , there is a unique polynomial of degree at most $n$ that interpolates all the data. The Lagrange form writes it as a weighted sum of basis polynomials.

The existence of a polynomial interpolant does not guarantee that high-degree interpolation is a good idea. Node placement and function behavior strongly influence accuracy.

Runge's Phenomenon and Better Node Choices

High-degree interpolation at equally spaced nodes can oscillate strongly near the ends of an interval. This is known as Runge's phenomenon.

Possible responses include using piecewise low-degree polynomials, splines, or node sets designed to control interpolation error, such as Chebyshev-type nodes. The lesson is broader than interpolation: increasing formal order does not automatically improve numerical results.

Splines and Approximation by Least Squares

A cubic spline uses piecewise cubic polynomials joined with smoothness conditions. Splines can provide local control and avoid the global oscillation of one very high-degree polynomial.

When data contain noise, exact interpolation may be undesirable. least-squares approximation instead minimizes a measure of discrepancy. In matrix form, an overdetermined system $A x \approx b$ can be solved through factorizations such as QR. Forming the normal equations can square the condition number, so QR-based methods are often preferable when numerical stability matters.

Numerical Linear Algebra

Large scientific computations frequently spend most of their time solving linear systems, least-squares problems, or eigenvalue problems. Numerical linear algebra therefore lies at the heart of numerical analysis.

Gaussian Elimination and Pivoting

Gaussian elimination transforms a linear system into an equivalent triangular system and then uses back substitution. In floating-point arithmetic, choosing a poor pivot can magnify errors. Partial pivoting reduces this risk by exchanging rows so that a sufficiently large pivot is used.

For repeated systems with the same matrix and different right-hand sides, an LU factorization can separate the expensive factorization stage from the cheaper triangular solves.

Iterative Methods

Direct methods aim to obtain a solution after a finite sequence of arithmetic operations in exact arithmetic. Iterative methods generate improving approximations and are often attractive for large sparse systems.

Classical stationary schemes include the Jacobi method and the Gauss–Seidel method. Modern large-scale problems often use conjugate gradients for suitable symmetric positive-definite systems and Krylov-subspace methods such as GMRES for more general systems. Preconditioning transforms the system so that an iterative solver converges more rapidly while preserving the original solution.

Residual, Error, and Condition Number

For an approximate solution $\hat{x}$ to $A x = b$ , the residual is

$r = b - A \hat{x} .$

A small residual is desirable, but it does not by itself prove that $\hat{x}$ is close to the exact solution. When $A$ is ill-conditioned, a small residual can coexist with a substantial forward error. This is why residual-based stopping rules should be interpreted together with conditioning.

Numerical Differentiation and Integration

Finite Differences

Derivatives can be approximated from sampled values. The forward difference

$f^{'} (x) \approx \frac{f (x + h) - f (x)}{h}$

has first-order truncation error for smooth functions, while the centered difference

$f^{'} (x) \approx \frac{f (x + h) - f (x - h)}{2 h}$

has second-order truncation error. Making $h$ smaller initially reduces truncation error, but an extremely small $h$ can increase the influence of round-off and cancellation. The best step size balances competing error sources.

Quadrature Rules

Numerical integration, also called quadrature, approximates a definite integral using function values. Composite rules divide the interval into smaller panels.

The trapezoidal rule replaces the curve locally by straight line segments. Simpson's rule uses quadratic interpolation over pairs of subintervals and is exact for polynomials up to degree three when applied in its standard one-panel form.

Gaussian quadrature chooses both nodes and weights strategically to achieve high polynomial exactness with relatively few evaluations. Adaptive quadrature estimates local error and refines only where the integrand is difficult.

Numerical Solution of Ordinary Differential Equations

An initial-value problem has the form

$y^{'} (t) = f (t, y), y (t_{0}) = y_{0} .$

A numerical ODE solver advances the state over discrete time points. Step size, order, stability, and error control interact strongly.

Euler's Method

The explicit Euler method is

$y_{n + 1} = y_{n} + h f (t_{n}, y_{n}) .$

It is easy to derive and implement, but it is only first-order accurate globally and may require very small steps for stability.

The explicit and implicit forms can behave very differently on stiff problems.

Runge-Kutta Methods

Runge-Kutta methods combine several slope evaluations within a step. The classical fourth-order Runge-Kutta method is widely taught because it achieves high accuracy without requiring higher derivatives of $f$ .

Modern solvers often use embedded Runge-Kutta pairs to estimate local error and adapt the step size automatically.

Stiffness and Stability Regions

A problem is called stiff when stability restrictions force some explicit methods to take much smaller steps than accuracy alone would require. Implicit methods can have much larger stability regions and are therefore important for stiff systems. Understanding stiffness requires you to distinguish the properties of the differential equation from the properties of the time-stepping method.

Algorithm Design, Implementation, and Verification

A numerical method becomes useful only when the mathematical idea is translated into a trustworthy computational procedure.

A Reproducible Workflow

Mathematical model: State the problem, assumptions, input units, and desired output clearly.
Sensitivity analysis: Determine how input perturbations can affect the solution.
Algorithm: Choose a method whose convergence, stability, and cost fit the problem.
Error estimation: Use theory, residuals, step refinement, or a posteriori estimators to quantify uncertainty.
Verification: Test the implementation on problems with known behavior and compare independent methods when possible.
Reproducibility: Record software versions, tolerances, parameters, and data transformations so results can be checked.

Convergence Studies

Suppose a discretization uses a step size $h$ and theory predicts an error proportional to $h^{p}$ . Repeating the computation with successively smaller $h$ should reveal the expected rate once the asymptotic regime is reached. If the observed rate is wrong, possible causes include a coding error, insufficient resolution, a nonsmooth solution, an inappropriate boundary treatment, or round-off dominance.

A convergence study turns theoretical order into empirical evidence. It is one of the most powerful habits in computational mathematics.

Cost, Memory, and Structure

The fastest algorithm on a small dense problem may be unsuitable for a huge sparse problem. Exploiting matrix symmetry, sparsity, banded structure, repeated right-hand sides, or parallelism can change the best method. Numerical analysis therefore evaluates algorithms not only by mathematical correctness but also by arithmetic complexity, data movement, memory use, and robustness.

Worked Connections Across Methods

Consider computing a quantity that depends on a parameter found implicitly by a nonlinear model. You might first solve a root problem for the parameter, then solve a linear system inside each model evaluation, interpolate measured coefficients, integrate a response curve, and finally advance a differential equation. Each stage introduces its own error and sensitivity.

This chain illustrates why numerical methods should not be studied as isolated recipes. Error propagates across stages, and improving a very accurate component may be pointless if another stage dominates the uncertainty. A mature numerical analysis asks where accuracy is needed, where it is lost, and what computational effort is justified.

Further University-Level Topics

Once you understand the core methods in this course, natural extensions include eigenvalue algorithms, singular value decomposition, numerical optimization, fast Fourier transforms, Monte Carlo methods, finite elements, finite differences for partial differential equations, spectral methods, randomized numerical linear algebra, interval arithmetic, and high-performance scientific computing.

These areas preserve the same central questions: approximation, convergence, stability, conditioning, complexity, and verification.

Interactive Tasks

Quiz: Test Your Knowledge

What is the main purpose of numerical analysis? (To design and study reliable algorithms for approximate numerical solutions) (!To replace every mathematical proof with computer output) (!To guarantee that all decimal answers are exact) (!To avoid using mathematical models)

Which expression defines absolute error? (The magnitude of the exact value minus the approximation) (!The approximation divided by the exact value) (!The square of the residual) (!The number of digits printed by software)

What condition supports the standard bisection method for a continuous function? (The endpoints have function values with opposite signs) (!The derivative is constant everywhere) (!The interval contains no root) (!The initial guess is already exact)

What local convergence behavior is associated with Newton's method near a simple root under suitable conditions? (Quadratic convergence) (!No convergence) (!Constant convergence) (!Random convergence)

What can happen with high-degree polynomial interpolation at equally spaced nodes? (Large endpoint oscillations can appear) (!All rounding error disappears) (!Every derivative becomes exact) (!The polynomial becomes piecewise constant)

Why is partial pivoting used in Gaussian elimination? (To reduce the risk of error growth from poor pivots) (!To turn every matrix into the identity before solving) (!To remove the need for back substitution) (!To guarantee a condition number of one)

For which polynomial degree is the trapezoidal rule exact on one panel? (Linear polynomials) (!Quadratic polynomials only) (!Quartic polynomials only) (!No polynomials)

What is a standard exactness property of Simpson's rule on one panel? (It is exact for polynomials through degree three) (!It is exact only for constant functions) (!It is exact for every smooth function) (!It requires no function evaluations)

What is the global order of the explicit Euler method under standard smoothness assumptions? (First order) (!Second order) (!Fourth order) (!Infinite order)

Which statement correctly distinguishes conditioning from stability? (Conditioning describes the problem while stability describes the algorithm) (!Conditioning and stability are identical concepts) (!Conditioning describes only programming language syntax) (!Stability is a property only of the input data)

Memory Game

Condition number	Measure of sensitivity of a problem such as a linear system to perturbations
Bisection method	Bracketing procedure that repeatedly halves an interval containing a sign change
Pivoting	Row exchange strategy used to reduce problems caused by small elimination pivots
Interpolation	Construction of a function that matches prescribed data values at selected nodes
Quadrature	Numerical approximation of a definite integral
Runge-Kutta	Family of time-stepping methods that combines several slope evaluations within a step

Drag and Drop

Match the correct terms.	Topic
Uses a sign-changing interval	Bisection method
Uses a tangent slope	Newton's method
Uses basis functions through data nodes	Lagrange interpolation
Uses row operations on a linear system	Gaussian elimination
Uses weighted function values to approximate an integral	Numerical quadrature

...

Crossword Puzzle

Bisection	Which bracketing method repeatedly halves an interval containing a sign change?
Newton	Which root-finding method uses a derivative to form a tangent update?
Pivoting	What row-exchange strategy improves the robustness of elimination?
Interpolation	What process constructs a function through prescribed data points?
Quadrature	What is the numerical evaluation of a definite integral called?
Stability	What algorithmic property concerns control of computational error growth?

LearningApps

Cloze Text

Numerical analysis studies algorithms that compute

to mathematical quantities. The difference between an exact value and a computed value can be measured by

. A problem that strongly magnifies small input changes is called

. The bisection method preserves a root-containing

. Newton's method uses derivative information to form a

update. Polynomial interpolation constructs a function that passes through selected

. Partial pivoting improves Gaussian elimination by selecting a safer

. Numerical integration is also called

. The explicit Euler method advances an ODE solution using the current

. A Runge-Kutta method can combine several slope evaluations within one

. A convergence study checks whether observed errors decrease at the expected

. Reliable scientific computing also requires independent

.

Open-Ended Tasks

Easy

Error analysis: Compute absolute and relative errors for five approximations of quantities with very different scales, then explain which error measure is more informative in each case.
Bisection method: Create a hand-drawn or digital iteration diagram for a continuous function with a bracketed root and annotate how the interval changes.
Floating-point arithmetic: Write a short experiment in Python, Julia, MATLAB, or another language that compares two algebraically equivalent formulas and identifies a case where cancellation matters.
Numerical integration: Produce a visual comparison of the midpoint, trapezoidal, and Simpson rules for one smooth function and describe the geometric idea behind each approximation.

Standard

Newton's method: Implement Newton and bisection for the same nonlinear equation, compare convergence histories, and explain when you would prefer the slower method.
Interpolation: Sample a smooth function at equally spaced nodes, increase the polynomial degree, visualize the result, and investigate whether endpoint oscillations appear.
Gaussian elimination: Solve a linear system with and without partial pivoting, record residuals, and explain how pivot choice can affect numerical behavior.
Euler method: Solve one initial-value problem with several step sizes, estimate the observed convergence order, and present your results in a table or plot.

Advanced

Condition number: Construct or find two linear systems with very different condition numbers, perturb the right-hand side, and analyze how the solution changes relative to the data.
Adaptive quadrature: Design an adaptive integration experiment that refines difficult subintervals more than smooth ones and compare function-evaluation counts with a uniform composite rule.
Stiff equation: Compare an explicit and an implicit time-stepping method on a stiff test problem, then explain the difference using numerical stability rather than accuracy alone.
Scientific computing: Conduct a mini-project in which you reproduce a numerical result from a paper, textbook, laboratory problem, or open dataset and document assumptions, tolerances, software, verification tests, and limitations.

Learning Assessment

Method selection: Given three computational problems with different smoothness, scale, and reliability requirements, justify a numerical method for each and identify the main failure risk.
Error propagation: Analyze a multistage computation in which an interpolated quantity is used inside an integral and explain how uncertainty from one stage can influence the final result.
Root-finding comparison: Compare bisection, Newton, and secant methods on a nonlinear equation using convergence rate, robustness, derivative cost, and stopping criteria.
Linear system reliability: For a computed solution of a linear system, interpret the residual together with a condition estimate and decide whether the result is trustworthy.
Convergence study: Use numerical data from at least three resolutions or step sizes to estimate an observed order and explain whether it supports the theoretical prediction.
ODE solver choice: Evaluate whether an explicit Runge-Kutta method is appropriate for a given initial-value problem and defend your answer using accuracy, stability, stiffness, and computational cost.

Evidence of Learning

Knowledge: You can explain approximation error, round-off, truncation error, conditioning, stability, convergence order, residuals, and the mathematical ideas behind representative numerical methods.

Skills: You can implement and test root finders, interpolation methods, linear solvers, quadrature rules, and ODE methods; perform convergence studies; choose stopping criteria; and interpret numerical diagnostics.

Products: Strong evidence includes reproducible code, convergence plots, error tables, annotated visualizations, short technical reports, solver comparisons, and clearly documented computational experiments.

Transfer achievements: You can recognize numerical structure in an unfamiliar applied problem, select a suitable algorithm, anticipate sensitivity and failure modes, verify the computation independently, and communicate what the numerical answer does and does not establish.