Keep the Courant number fixed and write . An exact solution of is . Substituting it into the update gives the defect
where and is evaluated at . The constant, first-derivative and second-derivative terms cancel. Dividing by gives a second-order consistency error. Hence for fixed , , the scheme has order two.
At the special value , the update reduces to . This is exactly the transport over two time steps, since , so the defect vanishes identically. With exact data at both starting levels it transports their values exactly; errors in those starting levels are still present, and the even and odd time subsequences evolve separately.
With , , and , the Forward Euler method gives
For a Fourier mode , the amplification factor is . Set . Then
The expression in braces is an affine function of , so it is nonpositive for all precisely when its two endpoint values are nonpositive. For , these conditions are and . Thus Forward Euler stability for centered advection-diffusion requires exactly
For , only the first condition remains. If either bound fails, a band of Fourier modes has , giving instability under von Neumann stability analysis. At equality the amplification bound still holds, so the endpoints are included. This is discrete L2 norm stability; nonnegative stencil weights would impose the additional spatial restriction .
Write and set . In the discrete L2 norm , the energy method gives
To obtain this identity, shift the indices in the centered second-difference sum. The centered first-difference matrix is skew-symmetric, so its contribution has zero real part even for complex grid values. The homogeneous Dirichlet boundary conditions remove the endpoint terms.
Therefore the semidiscretization is stable for every real and every positive , with the mesh-independent bound . No restriction on is needed for this energy estimate.
For algebraic stability, the weights must be nonnegative and the real symmetric matrix , where , must be a positive semidefinite matrix.
The weights are positive, but and , so
A positive semidefinite matrix cannot have a negative diagonal entry, as its quadratic form at the first standard basis vector would be negative. Thus this Lobatto IIIA method is not algebraically stable, despite its A-stability.
The stability function of a Runge-Kutta method is . Substitution gives
Writing the numerator and denominator as and ,
The denominator has zeros , both in the right half-plane. Therefore throughout the closed left half-plane, with strict inequality in its interior. The method is A-stable. Since at infinity, it is not L-stable.
The tableau is the three-stage Lobatto IIIA method. For its stage matrix , weights , nodes and , the Butcher order conditions through order four are
where means coordinatewise powers. Direct substitution verifies all eight identities. Equivalently, this is a collocation Runge-Kutta method at the three Lobatto quadrature nodes, whose weights integrate cubic polynomials exactly.
Order five would require , but here . Therefore the method has exactly order four.
For the Dahlquist test equation, put . The amplification roots satisfy
We show that no root can reach the unit circle for . If , solving the quadratic in gives
Write , , and . Then and
Since , this gives . Consequently , so both possible have nonnegative real part. Equality can occur only at , which gives or .
The leading coefficient has zeros , both in the right half-plane. Hence the amplification roots vary continuously as a pair throughout the left half-plane. At they are and ; neither can leave the unit disk without crossing the unit circle, which the preceding calculation excludes. The same conclusion extends to the imaginary axis, with strict inequality away from . At zero the roots satisfy the simplicity requirement.
Thus the method is A-stable. Its third order does not contradict the usual second-order barrier, because it is a multiderivative multistep method.
Expand about and use from the chain rule. The residual of the exact solution is
The coefficients through vanish, and the displayed fourth-order coefficient does not. Thus the multiderivative multistep method has order three.
At , its first characteristic polynomial is
Its roots are and , with the unit-modulus root simple, so it satisfies the root condition for a multistep method and is zero-stable. Combining this with the defect estimate proves convergence of order three, assuming sufficiently smooth , order-three starting values, and the nearby branch of each implicit update.
More explicitly, the right-hand side is , where has a uniform local Lipschitz continuity bound for small . A bounded zero-stable impulse response and the discrete Gronwall inequality therefore control the accumulated defects by over fixed time intervals. This is convergence of a zero-stable multiderivative method, rather than a direct application of the first-derivative-only Dahlquist equivalence theorem.
Let . Direct multiplication gives , so .
Suppose , where is a positive semidefinite matrix and is a symmetric nonnegative matrix. Since , both and are nonnegative. Their sum is zero, so both vanish. In particular,
Every coefficient in this sum is strictly positive and every is nonnegative, forcing for .
Now apply the same argument to all five cyclic shifts of . The Horn copositive matrix is cyclically invariant, so every shifted vector also has zero quadratic form. It follows that the entries of vanish on every cyclic block of three consecutive indices. Every pair of indices on a five-cycle lies in such a block, hence .
This would imply . But the zero quadratic form of a positive semidefinite matrix would then force , contradicting . Therefore lies outside the positive-semidefinite-plus-nonnegative cone. By the previous equivalence, its quartic form is a nonnegative polynomial that is not a sum of squares polynomial.
The Horn copositive matrix is invariant under cyclic permutation of its five coordinates: its negative entries correspond precisely to neighboring indices on the five-cycle. For any , cyclically relabel the coordinates so that is a smallest coordinate. In particular, .
Using the stated identity in this coordinate order,
The square is nonnegative, and both remaining terms are nonnegative since and . Cyclic invariance means the relabeling has not changed the quadratic form. Thus is a copositive matrix for every original ordering of .
First suppose , with a real positive semidefinite matrix and a symmetric nonnegative matrix. Factor , and write . Then
Each term is a square multiplied by a nonnegative scalar, so is a sum of squares polynomial.
Conversely, suppose . Because is a degree-four homogeneous polynomial, the homogeneous sum of squares representation allows every to be quadratic and homogeneous. Explicitly, higher-degree parts cannot cancel in a sum of squares; constant parts vanish because , and the degree-two part forces all linear parts to vanish. Write
Since is invariant under every coordinate sign change, sign averaging of a sum of squares over independent Rademacher random variables gives
The cross terms vanish because their sign products contain an odd power of at least one independent sign. Set
Then is a positive semidefinite matrix and is a symmetric nonnegative matrix. Comparing the coefficients of and gives . This proves the sum of squares criterion for a biquadratic form.
For , define . Then lies in the nonnegative orthant and
If is a copositive matrix, this is nonnegative for every , so is a globally nonnegative polynomial. Conversely, every has the form by taking . If is globally nonnegative, then for every such , proving that is a copositive matrix. The map covers the entire nonnegative orthant, which is the key to both directions.
For a proper three-graph colouring , associate the colors with the three roots of unity , viewed as unit vectors in . Define using the real inner product.
This is twice a Gram matrix, so it is a positive semidefinite matrix. Its diagonal is . On every edge, the endpoint colors differ, so their vectors make angle or and . Thus and this are feasible in the second semidefinite program, proving
This is the regular simplex construction of a strict vector coloring.
Let be the all-ones matrix. Every feasible block matrix in the first formulation has , because its principal submatrix on indices is and is a positive semidefinite matrix. In particular, .
By the Schur complement,
Set . Then , , and on every edge. Conversely, for a feasible in the second formulation, its nonnegative diagonal gives , and has , on edges, and .
Both transformations preserve the objective . Hence the two semidefinite programs defining the complement theta number have the same feasible objective values and the same minimum.
Replace coordinate inequalities by the Loewner order and coordinate sums by matrix trace. The maximizing semidefinite program is
Its feasible set is the fantope. In an orthonormal eigenbasis of , its objective is , and the diagonal entries of belong to the capped simplex. Choosing as the orthogonal projection matrix onto the largest eigenvectors attains the sum of the largest eigenvalues, as in the Ky Fan maximum principle.
The minimizing semidefinite program is
For example, its Lagrangian arises by assigning to , keeping in the domain, and using free for . Finiteness of the supremum over requires .
Equality follows directly by choosing to have eigenvalues in the same orthonormal eigenbasis, with between the th and st eigenvalues, or below the smallest one for . This is the threshold semidefinite program for the largest eigenvalues, and it also verifies the endpoint case .
Substitute the dual linear program from the previous part and optimize jointly over . The result is
The objective is linear, and the constraints are equalities or inequalities between affine functions, so this is a linear program. For each fixed feasible , minimizing over gives exactly by the threshold formula for the sum of the largest components; hence the reformulation preserves the optimal value and optimal whenever an optimum exists.
Keep as the domain restriction, introduce nonnegative Lagrange multipliers for , and introduce a free multiplier for . The maximizing Lagrangian is
Its supremum over is finite exactly when , and then equals . By linear programming duality, since the primal is feasible and bounded,
Minimizing over for fixed gives , the positive part of a real-valued function. Thus the threshold formula for the sum of the largest components is
For a direct attainment check, order the coordinates . Any is optimal for , while any is optimal for .
The required linear program is
There are inequality constraints and one equality constraint, all independent of .
The feasible set is the capped simplex, a nonempty compact set. A linear function attains its maximum at an extreme point; the previous part identifies these as the indicators of -element subsets. At such a vector, the objective is the sum of the selected coordinates. Maximizing selects the largest coordinates, including when some are negative or tied. Equivalently, is the support function called the sum of the largest components.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact