Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 72 2 c Solution 2026-10-14
Apply the method to the Dahlquist test equation, put , and retain every root of its amplification polynomial of a multistep method:An A-stable convergent method must satisfy the root condition for a multistep method for every .
First take . As negative real tends to minus infinity, one root tends to the nonzero root of ,It follows by root continuity that some sufficiently negative finite is unstable. At , the recurrence has polynomial ; for any negative real , its root is below . Thus all negative convergent parameters are excluded.
For , use the boundary-locus test for multistep A-stability. A unit root with would require . Direct multiplication by the conjugate denominator givesThere is therefore no unit-root crossing in the open left half-plane. The leading coefficient of never vanishes there, since its only zero is the positive real value . For a small negative real , the simple root initially at one moves to , inside the disk, and the other root is close to , also inside. Continuity of polynomial roots and connectedness of the open left half-plane then keep both roots strictly inside throughout that half-plane. Possible zeros of cause no omitted crossing: for its other root lies strictly inside the unit disk, while at its unit-circle zero has .
On the imaginary axis, if the displayed real part vanishes only at , which corresponds to and is simple. Other imaginary-axis parameters retain strictly interior roots. If , the two roots are zero and the stability function , whose modulus is one on that axis; the unit root is simple. Thus the required boundary root condition for a multistep method holds as well.
Combining necessity and sufficiency givesIn particular, the third-order member is convergent but not A-stable, in agreement with the Second Dahlquist barrier.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 72 6 Solution Created 2026-10-03 Updated 2026-10-14
The eigenvalue stability analysis of a finite difference method reduces a linear evolution discretization to its modal behavior, but it must retain the norm and the dependence on the mesh. For a homogeneous system obtained by the method of lines, , the solution is . A one-step time discretization gives ; for a Runge-Kutta method, where its stage matrices are invertible, . With a multistep method one instead uses an amplification matrix on the augmented vector of several time levels.
The relevant finite-time stability estimate iswith independent of the refining spatial mesh and allowed time steps. Similarly, semidiscrete stability requires for . The norm should represent the continuum problem, such as the discrete L2 norm in one dimension. A fixed finite matrix having decaying solutions as is not by itself a mesh-uniform result for the partial differential equation.
If , thenThus eigenvalues of modulus at most one give a uniform bound when the diagonalizing bases have uniformly bounded condition numbers. For a normal matrix in the chosen inner product, the spectral theorem for normal operators supplies an orthonormal basis, so the condition number is one and the norm of is exactly . For a self-adjoint or skew-adjoint spatial matrix, applying a scalar stability function preserves this favorable modal structure. This is the setting where eigenvalue calculations provide especially clean, reliable step restrictions.
A precise fixed-matrix statement is also useful: a matrix is power bounded for all nonnegative integers if and only if all its eigenvalues lie in the closed unit disk and every Jordan block at a unit-modulus eigenvalue has size one. Indeed, powers of an interior Jordan block contain a polynomial in times a decaying geometric factor and are bounded; a larger block on the unit circle produces unbounded polynomial growth. For a family of matrices, the resulting bounds must still be uniform. Moreover, finite-time stability versus power boundedness distinguishes this all-time condition from the physical-time estimate above. For example , , has , bounded for despite a nontrivial Jordan block at one. Even the scalar update is stable on fixed intervals, since , although it represents a growing equation rather than a contraction.
For a constant-coefficient periodic difference operator, Fourier modes diagonalize the spatial matrix. The discrete Fourier transform is a unitary operator, so Parseval's identity identifies its modal maximum with the operator norm. The eigenvalue stability analysis of a finite difference method then becomes von Neumann stability analysis. For the Dirichlet discrete Laplacian, a discrete sine transform plays the same role. These facts explain its advantages: a large matrix calculation becomes a scalar symbol or a known spectral interval, and the extremal eigenvalue directly determines a safe time step.
As a first example, centered space discretization of the heat equation has eigenvaluesForward Euler method gives with . Requiring all factors in yields for all periodic meshes. In two dimensions the corresponding uniform bound is . Because these are normal matrices, these scalar bounds prove contraction rather than merely suggest it.
Backward Euler method has , so the centered discretization of the heat equation is contractive for every . The Crank-Nicolson method has and is likewise contractive for these negative real modes. However, its factor tends to for very stiff modes, leaving high-frequency oscillations weakly damped; Backward Euler method tends to zero. The eigenvalues therefore expose the presence of stiff differential equations and damping as well as binary stability. Unconditional stability does not remove accuracy requirements.
For an advection equation example, the upwind finite difference scheme for , , has factor , with . Sinceit is a contraction in the periodic discrete L2 norm exactly for . In contrast, Forward Euler method with centered advection has factor . Its modulus exceeds one at nonzero active frequencies, and repeated amplification makes it unstable under fixed nonzero Courant refinement. A much smaller scaling can bound its finite-time growth, demonstrating again that exact contraction and the most general stability estimate are different claims.
The major limitation is the possible presence of a nonnormal matrix. For example,Both eigenvalues are negative, yet at the second unit vector is amplified by at least . This proves that negative spectra do not imply uniform semidiscrete stability. Ill-conditioned eigenvectors, Jordan normal form and transient amplification can invalidate a spectral-only argument. Direct energy estimates or estimates for the resolvent can supply the missing norm control.
Boundary conditions are another limitation. A periodic symbol proves a periodic or whole-line result, not an arbitrary initial-boundary-value problem. Boundary closure of a difference scheme can introduce growing modes or mesh-dependent amplification. A spatial operator with variable coefficients can still be studied through its assembled matrix, but then whether it is a normal matrix, its condition number and the physical inner product must be checked rather than borrowed from a Fourier stability analysis. For the finite element method the natural mass matrix inner product often turns a generalized eigenvalue problem into a self-adjoint one.
For time-dependent or split updates, separate spectra are insufficient to control products. For instance, and each have only zero eigenvalues, while has eigenvalue . For , alternating the two is unstable. A common contractive norm would control the products, but their individual eigenvalues do not.
Finally, stability and consistency of a numerical method have different roles. The Lax equivalence theorem states that, for a well-posed linear initial-value problem and a consistent finite difference method on compatible grid spaces, stability on every fixed time interval is equivalent to convergence of a numerical method as the admissible meshes refine. Bounded grid representation and the correct initial and boundary setup are part of that framework. An eigenvalue estimate can establish its stability hypothesis in the favorable settings described above; it neither proves consistency of a numerical method nor bypasses its uniformity requirements. The method is therefore a powerful modal tool, provided its spectral calculation is connected to a genuine norm estimate.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 72 7 Solution Created 2026-10-03 Updated 2026-10-14
A fixed-step linear multistep method for uses several previous solution and derivative values:The coefficients are fixed independently of the step size. It is explicit when and implicit otherwise. Its characteristic polynomials of a linear multistep method are and . The contraction mapping theorem gives a uniquely solvable implicit step under a Lipschitz continuity bound whenever , by contraction of the new-value equation on the appropriate solution region. A suitable starting procedure must supply the first values; the method alone does not determine them.
Order is defined by inserting a smooth exact solution into the recurrence. If the residual is and its first nonzero coefficient occurs at that degree, the method has order ; dividing the residual by gives an local truncation error. Taylor expansion gives the exact order conditions for a linear multistep methodwith the right side interpreted as zero at , and failure at for exact order. Equivalently,The basic consistency of a numerical method conditions are , ; for the ordinary nondegenerate consistent formulation this common value is nonzero. Exactness on constants and linear functions does not control propagation of numerical perturbations.
That propagation is the role of zero-stability. On the homogeneous recurrence is . Its modes are , with powers of determined by root multiplicities. The theorem on the root condition for a multistep method states that zero-stability is equivalent to every root of having modulus at most one, with every unit-modulus root simple. Interior repeated roots are permitted, since geometric decay dominates their polynomial factors. An exterior root amplifies perturbations geometrically; a repeated unit root amplifies them polynomially and violates a step-independent perturbation bound.
The Dahlquist equivalence theorem states that a fixed-step consistent linear multistep method is convergent exactly when it is zero-stable. This concerns ordinary differential equations with a uniformly Lipschitz continuous right-hand side on the solution region over a fixed finite interval, convergent starting values, and the well-defined nearby branch of each small-step implicit solve. For order convergence of a numerical method, the solution must have the required smoothness and the starting errors must be .
The mechanism can be sketched explicitly. The root condition for a multistep method bounds the recurrence's discrete Green function. For an order- exact-solution defect , the Lipschitz continuity error equation then gives an estimate of the formThe current-step term can be absorbed for small . The discrete Gronwall inequality says that a bound implies . There are defects on a fixed interval, so their sum is and this yields the claimed global order. Conversely, testing with vanishing starting perturbations in exterior-root or repeated-unit-root modes proves that convergence of a numerical method fails without the root condition for a multistep method.
For example, the two-step Adams-Bashforth method hasIt is explicit, order two and zero-stable, hence convergent with order-two starting values. By contrast, a recurrence with has solutions on the zero differential equation. Starting differences tend to zero yet become unbounded at a fixed positive time, since is of order . A small local defect or formal high order cannot rescue this mode. Canceling a common factor may remove it only by changing the allowed starting relations, as the parameter endpoint in Question 2 illustrates.
Absolute stability addresses a different limit: apply the method to the Dahlquist test equation and put . The amplification roots satisfyAll roots must satisfy the disk condition, with unit roots simple; one cannot inspect only the root that tends to one as . The degree and solvability of the recurrence must also be preserved. The resulting set of is the domain of absolute stability. A-stability means that it includes the whole closed left half-plane, so the numerical solutions of every Dahlquist test equation with are stable for every positive step size. It is a linear test-equation property, not a proof of arbitrary nonlinear contractivity or high accuracy at large steps.
Forward Euler method has order one and factor , so its stability region is the disk . Backward Euler method has factor and is A-stable. The trapezoidal rule is order two with factor ; its modulus is at most one throughout the left half-plane. These one-step methods are included as the simplest multistep examples. For the two-step Adams-Bashforth method, the negative-real stability interval is : its polynomial is , and the root reaches at . It therefore imposes a step restriction when applied to strongly decaying modes.
The genuinely two-step BDF2 method isIt has order two, roots at zero step and is A-stable. For its normalized polynomials , , the unit-circle boundary locus hasThe leading coefficient has no zero in the left half-plane, and the roots at a small negative are both inside the disk. Root continuity then proves open-half-plane stability; on the imaginary boundary the only possible unit root is the simple root one at . This gives a direct proof of the stated A-stability rather than relying on a boundary plot.
Two sharp order barriers explain the tradeoff. The first Dahlquist barrier states that a consistent zero-stable real linear -step method using only first derivatives has order at most for odd and for even ; an explicit method has order at most . The Second Dahlquist barrier states that an irreducible A-stable real linear multistep method has order at most two. These statements concern fixed constant coefficients and the ordinary first-derivative multistep class, not multiderivative methods or arbitrary variable-step formulations. Thus higher order alone is not a route to unconditional stiff stability. Question 2 provides a concrete illustration: its third-order member is zero-stable but not A-stable.
No nontrivial consistent explicit multistep method is A-stable. Its amplification polynomial of a multistep method has a fixed highest coefficient, while at least one lower coefficient grows without bound as real . Were all roots uniformly in the unit disk, their elementary symmetric polynomials would keep all the monic coefficients bounded, a contradiction. This is the coefficient argument behind explicit multistep methods cannot be A-stable.
In practice, selecting a method therefore involves accuracy, startup, the presence of a stiff differential equation, implicit-solve cost and step-size control. Zero-stability handles propagation as the step tends to zero; consistency of a numerical method supplies a vanishing defect; A-stability handles the numerical solutions of all decaying Dahlquist test equations at finite steps. None substitutes for the others, and variable steps or PDE discretizations require additional uniform stability arguments appropriate to their setting.
Past exam of the mathematics course of the University of Cambridge 2009 ii Paper 1 18H Solution Created 2026-09-24 Updated 2026-10-14
A K-isomorphism is a field isomorphism fixing every element of . The field automorphism group consists of such isomorphisms , with composition.
If an isomorphism sends to , it takes every polynomial relation over for to the same relation for ; the monic minimal polynomials coincide. Conversely, if their common minimal polynomial is , evaluation induces field isomorphisms and . Their composite sends to and fixes .
An automorphism of sends to a root of inside and is determined by this image. More precisely the field automorphism group permutes the set of roots of lying in this field, a set of size . This action is faithful because fixing fixes the generated field. Thus embeds in , and then in by fixing extra labels. In particular it is finite. This argument also covers inseparable minimal polynomials.
For an example not isomorphic even as abstract fields, take , let generate over , and put . The constant-field minimal polynomial of remains irreducible over the rational function field: if it factored over , each monic factor's coefficients would be algebraic over , being symmetric functions of constant algebraic roots. A rational function algebraic over is constant, so those coefficients would lie in , contradicting the original irreducibility. The polynomial is irreducible by Eisenstein criterion at in . Both degrees are , butThe first field has roots of ; the second has only . Indeed a rational function algebraic over a finite constant field must be constant: a nonconstant rational function makes the transcendental variable algebraic over its own rational-function field, and therefore cannot itself be algebraic over the constants. The root counts are isomorphism invariants. These extensions are not isomorphic.
If is finite, every degree- extension is a field with elements. Such fields are splitting fields of over , so uniqueness of the splitting field gives a K-isomorphism. There is no finite-base-field example of this kind.
Past exam of the mathematics course of the University of Cambridge 2009 ii Paper 1 20H iii Solution Created 2026-09-24 Updated 2026-10-14
Write and . Since their common square-free discriminant is congruent to zero or one modulo four, it must be one modulo four; thus are odd. It is not a rational square because a square-free integer square is only zero or one. Both polynomials are irreducible over , and their roots generate the same quadratic extension . Their integral roots are and , respectively. Each generated order isthe usual ring of integers for square-free . This identifies both quotients with the same ring. Explicitly, if denotes the image of modulo , send the image of modulo to . Equal discriminants give , and the opposite translation gives its inverse. The two quotient rings are isomorphic.
Past exam of the mathematics course of the University of Cambridge 2009 ii Paper 1 22H c Solution Created 2026-09-24 Updated 2026-10-14
Let be the linear subspace of polynomials of degree at most . It has finite dimension , is proper in , and . For any norm on , the restricted norm on is equivalent to its coefficient Euclidean norm: on the coefficient unit sphere the continuous norm has a positive minimum and a finite maximum. Thus is complete. A complete subspace of a metric space is closed, since any sequence converging to an ambient limit is Cauchy and has the same limit in the subspace.
Part (b) makes each a closed set with empty interior, hence nowhere dense. If were a Banach space, this countable union would contradict the Baire category theorem. No norm makes the space of all polynomials complete.
Past exam of the mathematics course of the University of Cambridge 2009 ii Paper 1 23G a Solution Created 2026-09-24 Updated 2026-10-14
A rational function is a quotient of polynomials with . Cancel common factors. It determines a map on the Riemann sphere by assigning infinity at poles and assigning at infinity the limit in the sphere. Equivalently homogenize to the same degree and set . They have no common projective zero: finite ones would contradict coprimality, and at infinity at least one has a nonzero leading coefficient. This also proves the map is holomorphic.
The degree of the nonconstant rational function is . The degree of a holomorphic map of compact Riemann surfaces is the number of preimages of any target point, counted with local mapping multiplicity. For target , the homogeneous equation is a nonzero homogeneous polynomial of degree . Over it factors into linear factors, with multiplicity, giving exactly projective zeros. Locally its zero order is precisely the map's multiplicity, since the other target-coordinate denominator is nonzero. The two degrees are equal.
There is a Möbius transformation sending any ordered triple of distinct points to . When all are finite one can use ; the formulas for infinity are its limits. Define in the same way. Then sends to and restricts to a biholomorphism .
Past exam of the mathematics course of the University of Cambridge 2009 ii Paper 1 2F ii Solution Created 2026-09-24 Updated 2026-10-14
Use Gaussian quadrature: choose the nodes as the roots of the degree- Legendre polynomial, which are distinct and inside . Retain the integrated Lagrange interpolation weights. With the standard normalization , they can be writtenThe orthogonality of the Legendre polynomial against all lower-degree polynomials makes this quadrature exact up to degree , twice the arbitrary-node degree apart from the endpoint count. This is the Gauss–Legendre choice of Gaussian quadrature nodes and weights.
Past exam of the mathematics course of the University of Cambridge 2009 ii Paper 1 2F i Solution Created 2026-09-24 Updated 2026-10-14
Define the Lagrange interpolation polynomialsDistinct interpolation nodes ensure every denominator is nonzero and . For a polynomial of degree at most , the difference has degree at most and vanishes at distinct points, so it is zero. Integrating this Lagrange interpolation identity proves the required exact quadrature formula. This also covers , when the empty product is one and its weight is two.
Past exam of the mathematics course of the University of Cambridge 2009 ii Paper 2 12H Solution Created 2026-09-24 Updated 2026-10-14
The standard name is the Reed-Muller code. For , evaluate all multilinear polynomials over of total degree at most at every point of . These evaluation vectors form , of length . Distinct multilinear polynomials have distinct evaluations: induct on the variables using and the two restrictions . Thus the monomials of degree at most are independent andFor minimum weight, use the same splitting. A nonzero has weight at least by induction, and . If , the two identical halves give the same lower bound by induction on . The endpoint has minimum weight one, and is the repetition code. A product of distinct variables has exactly nonzero evaluations, soHere distance equals minimum nonzero weight because the code is linear.
Every monomial of degree at most in variables has an even number of ones, and parity is additive over . Thus every word of has even weight. If and , their coordinatewise product is an evaluation of degree at most , even after reducing . Its weight is therefore even, so . This proves the asserted inclusion in the dual code. Finallyby binomial symmetry. The dimensions agree with that of the orthogonal complement, proving for .
Past exam of the mathematics course of the University of Cambridge 2009 ii Paper 2 18H Solution Created 2026-09-24 Updated 2026-10-14
For the first polynomial, put and , so that . The roots are , andTo justify the degree, a rational quadratic factorization would have the form . The vanishing linear coefficient implies either or . The former requires , not rational, while the latter requires , also impossible over . There is no rational root, since its square would have to be , so the polynomial is irreducible. The real field has degree four and does not contain , giving degree eight after adjoining it. The group acts transitively on the four roots while preserving their two opposite pairs, so is contained in the square's dihedral group of order eight; the degree makes it the full group.
For the second polynomial, choose and . Then , and . Its four roots generateIndeed and recover both generators. The real quadratic field cannot contain , so the degree is four. Independent changes of the two square-root signs give all four automorphisms.