<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Simon on Medium]]></title>
        <description><![CDATA[Stories by Simon on Medium]]></description>
        <link>https://medium.com/@semen.tolstoguzov96?source=rss-01347f1bf6b0------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*7HG_hPBzDlIaamNW</url>
            <title>Stories by Simon on Medium</title>
            <link>https://medium.com/@semen.tolstoguzov96?source=rss-01347f1bf6b0------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 14:36:47 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@semen.tolstoguzov96/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[From PBD to XPBD: Simulating an Elastic Rope]]></title>
            <link>https://medium.com/@semen.tolstoguzov96/from-pbd-to-xpbd-simulating-an-elastic-rope-79e6eb6a2f33?source=rss-01347f1bf6b0------2</link>
            <guid isPermaLink="false">https://medium.com/p/79e6eb6a2f33</guid>
            <category><![CDATA[numerical-methods]]></category>
            <category><![CDATA[physics]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[game-development]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[Simon]]></dc:creator>
            <pubDate>Mon, 16 Nov 2026 10:30:29 GMT</pubDate>
            <atom:updated>2026-11-16T10:30:29.159Z</atom:updated>
            <content:encoded><![CDATA[<blockquote>Part 2: compliant constraints, tension forces and substepping on top of PBD</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cPKN_vxaL84-o__tN4l9ng.png" /></figure><p>In the <a href="https://medium.com/@semen.tolstoguzov96/position-based-dynamics-from-scratch-simulating-a-rope-7d53b37a5921">first article</a> (code and text are on <a href="https://github.com/Semen1996/pbd-method-rope">GitHub</a>) we derived the PBD method for an inextensible rope without external forces. Its final section listed what was left out: gravity, elastic constraints, tension forces and slow convergence on long chains. Here we go through all of these one by one. We will need three additions:</p><ul><li><strong>external forces</strong> — only the prediction step changes (Sec. 2);</li><li><strong>XPBD</strong> (<em>extended PBD</em>) [1] — constraints get compliance, and as a bonus the method starts computing forces (Sec. 3–6);</li><li><strong>small steps</strong> [2] — instead of many iterations within one step, we take many short steps with one iteration each (Sec. 7).</li></ul><p>The code for this article is on <a href="https://github.com/Semen1996/xpbd-method-rope">GitHub</a>.</p><p>The notation is the same as in the first article: particles 1, …, N, positions <strong>r</strong>_i, velocities <strong>v</strong>_i, inverse masses w_i, corrected positions <strong>p</strong>_i, link length l₀ = L/(N − 1). References like “Sec. 6.2 of the first article” refer to it.</p><h3>1. The Problem</h3><p>The rope is the same: particle 1 is fixed at point A = (0, 0), and particle N is held by a hand at point B(t). Three things change.</p><ul><li><strong>Gravity acts</strong> with acceleration <strong>g</strong> = (0, −g), g = 9.81 m/s².</li><li><strong>The rope is elastic</strong>: under load it stretches a little. How much is set by a property of the rope itself, not by the solver settings.</li><li><strong>We need forces</strong>: the tension in each link and the force with which the rope pulls on the hand.</li></ul><p>All quantities now have dimensions (SI), and the rope has a mass M. We split it equally among the particles: each link has mass M/(N − 1) and gives half of it to each of its two particles. An interior particle gets</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/760/1*zEyPMFxYxLWhKPiZxuBUwg.png" /></figure><p>while the ends are still kinematic: w₁ = w_N = 0.</p><p>In the first article the value of w itself did not matter, only ratios did. Now that is no longer the case: w is added to the link compliance (Sec. 4) and enters the forces (Sec. 6), so the mass must be the real one.</p><p>We use the same motion example as before: initially the rope is straight and lies along the x axis, then the hand moves toward point A and stops. The initial bend is no longer needed: gravity breaks the symmetry.</p><h3>2. Gravity</h3><p>In PBD, external forces act only in the prediction step. Previously a particle moved by inertia with its old velocity. Now the force first changes the velocity, and the step is made with the new one:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/855/1*KAldqLOx_rlpNCTM-3jXPg.png" /></figure><p>For gravity <strong>F</strong>_i = m_i·<strong>g</strong>, and the mass cancels:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/779/1*oB7yTUZ0gk3jumH82KAm-w.png" /></figure><p>This is done for interior particles only. The ends are kinematic: their positions are prescribed, and gravity does not act on them.</p><p>The remaining steps are unchanged: constraint projection, then velocity as the difference of positions. Without constraints such a particle would fall along a parabola. With constraints, the projection step takes away the part of the fall that the rope does not allow.</p><h3>3. Elastic Link</h3><h3>3.1 Compliance</h3><p>We now treat the link between particles i and i + 1 as a spring. The constraint function is the same:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/465/1*_dkDvKTuUPBfftlqKRFmdQ.png" /></figure><p>which is the elongation of the link. A spring of stiffness k has energy</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/285/1*C9tOgh2GXeIgrf-INaH6xg.png" /></figure><p>and pulls the particles with tension</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/228/1*JCj0qtRBQf_sVRhpKu3UfQ.png" /></figure><p>(Hooke’s law; a stretched link has T_i &gt; 0).</p><p>Instead of stiffness, XPBD uses its inverse — <strong>compliance</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/947/1*ACb6Jdx6aRZOdgDYhU-EhA.png" /></figure><p>Compliance tells how much the link stretches under a unit force. The reason is the same as for using inverse mass instead of mass: a rigid constraint has infinite stiffness, while its compliance is simply zero. At α = 0 the XPBD formulas do not break and reduce to the PBD formulas.</p><h3>3.2 Where to Get the Value</h3><p>Suppose the rope is made of a material with Young’s modulus E and has cross-sectional area S. Young’s modulus relates not force to elongation, but stress (force per unit cross-sectional area) to relative elongation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/288/1*QSijb7ggE2MSK9rbSh3d8A.png" /></figure><p>The area appears here because E is a property of the material, not of a particular rope: in a thick rope more fibers carry the load in parallel. Hence F = (ES/l₀)·Δl, i.e. a piece of length l₀ is a spring of stiffness ES/l₀. Therefore the compliance of one link is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/234/1*btZnlOxXgWlws5GLrLDuyA.png" /></figure><p>E and S are not needed separately; only the product ES (in newtons) enters the formula. It is called the axial (tensile) stiffness. For a real rope this is even more convenient: it is twisted from fibers, and it is unclear which cross-sectional area to take. So ES is usually measured directly for the whole rope.</p><p>Let us check that the rope as a whole then behaves the same for any number of particles. Under tension T each link stretches by αT, there are N − 1 links, and the total elongation is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/473/1*mKVPbZgMkmS377EzXGjuSg.png" /></figure><p>i.e. it does not depend on N. If instead of E and S we know the stiffness of the whole rope K = ES/L (force per unit elongation), then α = 1/(K(N − 1)).</p><h3>4. Deriving XPBD</h3><h3>4.1 The Implicit Step</h3><p>In the first article, position correction was introduced geometrically: move the particles so that the conditions hold. To get elasticity, we need to understand which mechanics problem this step corresponds to.</p><p>Let particle i be acted on by an external force <strong>F</strong>_i and the elastic force of the links <strong>f</strong>_i. Write one time step of the implicit Euler method:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1016/1*uwv2ear-sGotonMLwuBO_g.png" /></figure><p>The prime marks values at the end of the step. “Implicit” means that the elastic forces are evaluated at the new positions <strong>r</strong>′, which are not yet known. Thanks to this the method stays stable even for very stiff springs. Substituting the first equation into the second:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/883/1*Fvlu5YwB1AxuIceybskQNA.png" /></figure><p>The underbraced part is the predicted position from Sec. 2. Denote it <strong>q</strong>_i to distinguish it from the positions <strong>p</strong>_i that change during correction. Multiplying by m_i:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/780/1*G2O5fdl4Wyp-E6Ltc1QBDA.png" /></figure><p>The new position differs from the predicted one by the displacement that the elastic forces manage to produce during the step. The PBD correction step must find exactly this displacement.</p><p><strong>Connection with the first article.</strong> Equation (1) is the condition for the minimum of the function</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/658/1*7AhEfzFWVaUTckDJKFw7Lw.png" /></figure><p>where U is the elastic energy of all links. The first term is familiar from Sec. 6.2 of the first article: it is the mass-weighted deviation from inertial motion. There we minimized it under the hard condition C = 0. Now there is no condition; instead, its violation is penalized by the elastic energy. The stiffer the spring, the more expensive the violation, and as α → 0 the problem turns into the old one.</p><h3>4.2 The Multiplier</h3><p>From now on we denote the link index by j so as not to confuse it with the particle index i. The elastic force on particle i is minus the gradient of the energy U = Σ_j U_j, i.e. it is a sum of contributions from the links:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/964/1*Rw6I-xB2BnCz5a8iXTAzeQ.png" /></figure><p>The first equality is the definition of a potential force: for a small displacement d<strong>p</strong>_i its work <strong>f</strong>_i · d<strong>p</strong>_i equals the decrease in energy −dU = −∇_(<strong>p</strong>_i) U · d<strong>p</strong>_i. The last one is the chain rule applied to U_j = C_j²/(2α_j) from Sec. 3.1. For a rope link, ∇_(<strong>p</strong>_i) C_j is a unit vector along the link, and C_j/α_j = T_j is the tension, so we get Hooke’s law.</p><p>Substitute into (1). We denote the unknown positions by <strong>p</strong>, as in the first article:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/819/1*_GBE4BX8jcUuqNk7WB_1cA.png" /></figure><p>The sum runs over the constraints that involve particle i; for an interior rope particle these are its two neighboring links. Introduce the notation</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/643/1*9wOnQdwaqYsTSAZO6yy2kQ.png" /></figure><p>Then the single equation splits into two:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/851/1*rUyEzIVKoFcQLQ36Cg0vgA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/655/1*d8xmsMB58Hf4g4CZ8IqtMg.png" /></figure><p>Compare with PBD.</p><ul><li>Equation (2) is formula (2) of the first article, Δ<strong>p</strong>_i = λ w_i ∇_(<strong>p</strong>_i) C, only with the displacements from all constraints summed. The number λ_j is the same Lagrange multiplier.</li><li>Equation (3) replaces the condition C_j = 0. At α = 0 it turns into it.</li></ul><p>Why introduce λ_j instead of keeping C_j/α_j? For a rigid constraint C_j → 0 and α_j → 0, and their ratio is the indeterminate form 0/0. But λ_j remains a finite number. Its physical meaning is discussed in Sec. 6: it is the constraint force multiplied by Δt².</p><p>The quantity α̃ has the dimension of inverse mass: (m/N)/s² = 1/kg. This will be useful below.</p><h3>4.3 A Single Constraint</h3><p>We solve the system (2)–(3) the same way as in PBD: one constraint at a time, several passes. The difference is that each constraint now has its own number λ_j, which <strong>accumulates</strong> over the step. At the start of the step λ_j = 0 and <strong>p</strong> = <strong>q</strong>, so equation (2) holds.</p><p>Take constraint j. The current positions <strong>p</strong> and the current λ_j do not satisfy equation (3). We look for an increment Δλ after which it will hold.</p><p>By equation (2), if λ_j is increased by Δλ, the particles move by</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/697/1*aLCgK1agpWa8ByZvpK5lyQ.png" /></figure><p>We require equation (3) to hold afterwards and linearize C_j, as in Sec. 6.2 of the first article:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/928/1*Sfkc_9KVCO6giAYeqQjaHw.png" /></figure><p>Substituting the displacements (4):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/995/1*jrf3nkRRPuH0SBAFNN1y0w.png" /></figure><p>Hence</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/901/1*fldXkT-UaG2hYVxt-qJddg.png" /></figure><p>Then we update the multiplier and the positions:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/909/1*KpFME4AX6Jc0geKOGvo7-w.png" /></figure><p>At α = 0 formula (5) coincides with formula (3) of the first article. All of XPBD comes down to two new terms: α̃_j λ_j in the numerator and α̃_j in the denominator.</p><p>The derivation contains one simplification. The gradients in (4) are taken at the current positions, while equation (2) requires gradients at the final positions. The difference is of second order in the displacements; the authors of the method [1] drop it, and so do we.</p><h3>4.4 The Link</h3><p>For the link C_i = |<strong>p</strong>_i − <strong>p</strong>_(i+1)| − l₀ the gradients are <strong>n</strong> and −<strong>n</strong>, where <strong>n</strong> = (<strong>p</strong>_i − <strong>p</strong>_(i+1))/d and d is the current link length. We get</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*amNNT6ixUsKPqFOQ19VyLQ.png" /></figure><p>The signs are checked the same way as in the first article: for a stretched link Δλ &lt; 0, and particle i moves against <strong>n</strong>, i.e. toward particle i + 1.</p><p>What the new terms do.</p><p><strong>α̃ in the denominator.</strong> In PBD the error d − l₀ was shared between two particles in proportions w_i and w_(i+1). Now there are three participants: the link itself keeps a third share, proportional to α̃. On the first iteration (λ_i = 0) the particles remove the fraction (w_i + w_(i+1))/(w_i + w_(i+1) + α̃) of the error, and the rest remains as spring elongation. The link behaves like one more “particle” with inverse mass α̃. That is why it matters that α̃ and w have the same dimension.</p><p><strong>α̃λ_i in the numerator.</strong> Without this term each subsequent iteration would again remove a fraction of the remaining elongation, and with many iterations the link would become rigid. The term remembers how much this link has already been corrected during this step. The target of the iterations is now not C = 0 but C = −α̃λ_i: the elongation corresponding to the accumulated force.</p><h3>4.5 Why the Result Does Not Depend on the Number of Iterations</h3><p>The iterations stop changing anything when Δλ = 0 for all constraints. By formula (5) this means C_j + α̃_j λ_j = 0, i.e. equation (3) holds. Equation (2) holds by construction. Hence the iterations converge to the solution of system (2)–(3) — an implicit Euler step for a rope with springs of the given stiffness. The number of iterations does not appear in this system.</p><p>n_iter only determines how close we get to that solution. In PBD with a stiffness coefficient k, the iterations converge to C = 0 for any k, and softness arises only because they do not get there in time. In XPBD softness is built into the problem itself.</p><h3>5. Stretching and Compression</h3><p>The spring from Sec. 3 works both ways: a stretched link pulls the particles together, a compressed one pushes them apart. For a rope this is not the only reasonable option.</p><p><strong>Bilateral link.</strong> The condition C_i = 0 with compliance α. The link resists stretching and compression equally. The length of the polyline used to draw the rope is almost constant. This was the case in the first article (with α = 0).</p><p><strong>Unilateral link.</strong> A real rope cannot push: if you bring its ends together, it does not compress but folds. When a link is longer than the size of such folds, it has no reason to resist compression. The condition becomes an inequality:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/548/1*Eu3VT4hRq8TPlcbZDismpA.png" /></figure><p>particles may come closer, they just may not move farther apart than l₀.</p><p>The first article said that an inequality is corrected only when it is violated. In XPBD the multiplier accumulates, and the rule is more conveniently stated in terms of it: the link can only pull. A stretched link has λ_i &lt; 0, so we require</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/172/1*HqyEXl6fZUUSGr29a6HwsQ.png" /></figure><p>and clamp the multiplier after each update:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/479/1*c8CnOtl98m470FD8Iqn_1A.png" /></figure><p>so that λ_i + Δλ ≤ 0. Particle displacements are computed from the clamped Δλ.</p><p>Why clamping rather than a simple “skip if C_i ≤ 0”? With several iterations, a link may be stretched on the first one and slack on the second, after its particles have been moved by neighboring links. Then the accumulated tension must be given back, but no more than was accumulated. Clamping does exactly that. If there is one iteration and λ_i = 0 at the start, the rule reduces to the simple one: correct a stretched link, skip a compressed one.</p><p><strong>Different compliances.</strong> An intermediate option is to set two compliances, α₊ for stretching and α₋ for compression, and on each correction use the one matching the sign of C_i. A unilateral link is the limit α₋ → ∞. This works most simply with one iteration per step (Sec. 7), when there is no accumulated multiplier.</p><p><strong>Which to choose.</strong> At rest under gravity all links are stretched, and the variants do not differ. The difference shows in fast motions, when the hand pushes the rope along itself. Bilateral links preserve the drawn length of the rope, and they are a reasonable default. Unilateral links give a more “cloth-like” behavior and are appropriate for large links.</p><h3>6. Tension Force</h3><p>PBD does not compute forces. In XPBD they come for free — from the multipliers.</p><p>The force with which link j acts on particle i (Sec. 4.2) is expressed through λ_j:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/577/1*aYo8d-_7IzisH-1MctXwMw.png" /></figure><p>The formula also holds for a rigid constraint with α = 0, even though it has no energy. By equation (2) the constraint moved the particle by w_i λ_j ∇_(<strong>p</strong>_i) C_j, and a constant force <strong>F</strong> produces a displacement Δt² w_i <strong>F</strong> over a step (Sec. 4.1). Comparing the two gives the same force.</p><p>For a link the gradients are unit vectors along it, so the <strong>tension</strong> of link i is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/291/1*GJXltN6YxtU5sx7v9CCJNQ.png" /></figure><p>The sign is chosen so that a stretched link has T_i &gt; 0. If the link is elastic and the iterations have converged, then by equation (3) C_i = αT_i — Hooke’s law from Sec. 3.1.</p><p><strong>Force on the hand.</strong> The hand holds particle N, which belongs to one link, the last one. Its gradient with respect to <strong>p</strong>_N is −<strong>n</strong>_(N−1), where <strong>n</strong>_(N−1) points from the hand toward particle N − 1. The force with which the rope pulls the hand is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/795/1*eqxRkO8F7QSrCNnReEQghA.png" /></figure><p>It points away from the hand along the rope. To hold the end, the hand must apply the opposite force. Particle N is kinematic and the solver does not move it, but the force is still well defined.</p><p>Likewise for the anchor: <strong>F</strong>_A = −T₁ <strong>n</strong>₁, where <strong>n</strong>₁ points from particle 2 toward point A; the force points away from A along the rope.</p><p>Two remarks.</p><ul><li>T_i is the average force over the step. If the iterations have not converged, it is noisy. With substeps (Sec. 7) the formula uses the substep length, and the value should be averaged over the substeps of one frame.</li><li>The weight of the end particles is not included in these forces: gravity does not act on kinematic particles.</li></ul><p><strong>Verification.</strong> At rest, the forces on each interior particle are balanced. This gives three simple tests:</p><ul><li><strong>F</strong>_A + <strong>F</strong>_hand equals the weight of the interior particles (N − 2)·m·<strong>g</strong>;</li><li>the horizontal component of the vector T_i <strong>n</strong>_i is the same in all links;</li><li>the vertical component changes from link to link by mg.</li></ul><h3>7. Small Steps</h3><h3>7.1 The Idea</h3><p>XPBD made stiffness a parameter of the problem, but convergence stayed the same: a correction travels along the rope at one link per iteration, and a stiff rope with small n_iter still comes out stretchy.</p><p>In the first article, among the ways to fight this were “increase n_iter” and “decrease Δt”. The <em>small steps</em> method [2] claims that for equal cost the latter is better. The step Δt is split into n_sub <strong>substeps</strong> of length</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/293/1*hKhZOPcsXZcTYkj7jWxA4g.png" /></figure><p>and on each substep the whole cycle is performed — prediction, correction, velocities — but with only <strong>one</strong> correction iteration:</p><pre>repeat n_sub times:<br>    steps (1)–(4) with Δt_s instead of Δt and n_iter = 1</pre><p>The number of passes over the links is the same as with n_iter = n_sub on one large step. Only prediction and velocity updates are added on each substep, and they are cheap.</p><h3>7.2 Why It Works</h3><p><strong>Violations get smaller.</strong> The solver error grows with how strongly the prediction violates the constraints (Sec. 7.2 of the first article). In one substep the hand moves by δ/n_sub instead of δ. Gravity moves particles by g·Δt_s², i.e. n_sub² times less than over a full step.</p><p><strong>Errors add up favorably.</strong> A rough estimate: over one step gravity introduces a violation of order g·Δt². Over n_sub substeps the total is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/458/1*n_wpGTc9UfP0Kz6kbBY4Aw.png" /></figure><p>The error falls inversely with the number of substeps. Gauss–Seidel iterations on a long chain reduce the error much more slowly.</p><p><strong>Unfinished work is not lost.</strong> One iteration does not satisfy the constraints exactly. But the residual error is not thrown away: the next substep keeps correcting the same positions, and through the velocities the correction propagates further along the rope.</p><p><strong>Less numerical damping.</strong> Implicit Euler damps oscillations, the more so the larger the step. With small substeps the rope swings longer. For a frictionless model this is correct. If damping is needed, it should be introduced explicitly rather than relying on the method’s error.</p><h3>7.3 What Changes in the Formulas</h3><p><strong>Compliance.</strong> α̃ now contains the substep length:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/244/1*OHbI1dKVugyH5c8GlbzB_Q.png" /></figure><p><strong>Multiplier.</strong> It is reset at the start of each substep, and there is one iteration. Hence in formula (5) always λ_i = 0, and the term α̃λ_i vanishes:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/515/1*JXTrn197A22mM3cjfrOEAg.png" /></figure><p>There is no need to store λ_i between links. It is worth keeping only for the tension: T_i = −Δλ/Δt_s².</p><p><strong>Hand.</strong> The hand position must be set on each substep: <strong>p</strong>_N = B(t + s·Δt_s) for substep s = 1, …, n_sub. If the hand is put at its final point right on the first substep, it covers the whole path in Δt_s, and its velocity comes out n_sub times higher than the real one. When the hand position is known only once per frame (for example, it is the mouse pointer), it is linearly interpolated between the old and new values.</p><p><strong>Sweep order.</strong> Alternating the direction of the sweep over links is now conveniently done per substep: on even substeps from point A to the hand, on odd ones back.</p><h3>7.4 Limitations of the Method</h3><ul><li>At α = 0 a small residual stretchiness remains. It decreases as n_sub grows but does not vanish.</li><li>With very small Δt_s, round-off errors start to interfere in single-precision computations: the per-substep displacement is too small compared to the coordinates. In double precision this is not a problem.</li><li>Everything done on each substep besides the links is also repeated n_sub times. For a rope this is cheap, but expensive operations (such as collision detection) are usually kept at once per frame.</li></ul><p>Several iterations per substep are possible; then the full formula (5) with the accumulated λ_i is needed. But according to [2] it is better to spend the same passes on additional substeps.</p><h3>8. The Full Algorithm</h3><p>What changed compared to the algorithm of the first article:</p><ul><li>the step is split into substeps;</li><li>gravity is added to the prediction;</li><li>each link has a multiplier λ_i, and the correction formula contains the compliance α̃;</li><li>a link may be unilateral;</li><li>the tension is computed at the end.</li></ul><p>The step numbering (1)–(4) is the same as before.</p><pre>given: r(1..N), v(1..N), w(1..N) with w(1) = w(N) = 0,<br>       anchor A, hand motion B(t),<br>       l0, g, α, Δt, n_sub, n_iter (usually 1)</pre><pre>Δts ← Δt / n_sub<br>α̃   ← α / Δts²</pre><pre>for s = 1..n_sub:                                    // substeps<br>    for i = 2..N−1:                                  // (1) gravity and prediction<br>        v(i) ← v(i) + Δts · g<br>        p(i) ← r(i) + Δts · v(i)<br>    p(1) ← A                                         // (2) ends<br>    p(N) ← B(t + s · Δts)</pre><pre>    λ(i) ← 0  for i = 1..N−1                         // multipliers start at zero<br>    repeat n_iter times:                             // (3) constraint projection<br>        for i = 1..N−1:<br>            d  ← p(i) − p(i+1)<br>            dl ← |d|<br>            ws ← w(i) + w(i+1)<br>            if ws = 0 or dl = 0: skip<br>            Δλ ← −(dl − l0 + α̃ · λ(i)) / (ws + α̃)<br>            if link is unilateral:<br>                Δλ ← min(Δλ, −λ(i))                  //     link can only pull (Sec. 5)<br>            λ(i)   ← λ(i) + Δλ<br>            p(i)   ← p(i)   + w(i)   · Δλ · d / dl<br>            p(i+1) ← p(i+1) − w(i+1) · Δλ · d / dl</pre><pre>    for i = 1..N:                                    // (4) velocities and positions<br>        v(i) ← (p(i) − r(i)) / Δts<br>        r(i) ← p(i)</pre><pre>    T(i) ← −λ(i) / Δts²  for i = 1..N−1             // tension on this substep</pre><pre>force on hand:  T(N−1) · (r(N−1) − r(N)) / |r(N−1) − r(N)|</pre><p>With α = 0, g = 0, n_sub = 1 and bilateral links this is exactly the algorithm of the first article.</p><p>An early exit based on tolerance ε is not needed with one iteration. With several iterations, the link error is no longer |C_i| but |C_i + α̃λ_i|: an elastic link has C_i ≠ 0 even in the solution.</p><h3>9. Example Parameters</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/932/1*UZEnfgA34EnNzpZqyr1lYQ.png" /></figure><p>The number of substeps is chosen empirically; typically it is tens per frame.</p><p>How “soft” a link is for the solver is shown by comparing α̃ with w_i + w_(i+1) = 980 kg⁻¹. Three cases:</p><ul><li><strong>Rigid rope</strong>, α = 0. Then α̃ = 0, and we get PBD with substeps.</li><li><strong>Stiff rope</strong>, K = 1000 N/m (1 mm of elongation per newton). The link compliance is α = 1/(K(N − 1)) ≈ 2.04·10⁻⁵ m/N, so α̃ = α/Δt_s² ≈ 29 kg⁻¹. The link keeps 29/(980 + 29) ≈ 3 % of the error per pass. The rope weighs about 1 N, so the stretch under its own weight is about a millimeter.</li><li><strong>Rubber band</strong>, K = 10 N/m. Then α ≈ 2.04·10⁻³ m/N and α̃ ≈ 2900 kg⁻¹ — more than w_i + w_(i+1). The link keeps three quarters of the error, and the rope stretches noticeably under its own weight — by centimeters.</li></ul><p>Note that α̃ grows as the substep shrinks. This is correct. Over a short time the spring manages to move the particles less, and a smaller fraction of the elongation is corrected on each substep.</p><p><strong>How to verify the simulation.</strong> Besides the force tests from Sec. 6, two more are useful:</p><ul><li>at α = 0 the shape of the rope at rest should match the catenary;</li><li>at α &gt; 0 the elongation of the rope at rest should not change if n_sub or n_iter is changed. In PBD with a stiffness coefficient k it would change.</li></ul><h3>10. What’s Next</h3><ul><li><strong>Damping.</strong> The model has no friction, and with small substeps the rope swings for a long time. The simplest approach is to slightly reduce the velocities of interior particles on each substep. XPBD [1] also offers a more careful option: damping is built into the constraint itself and damps only the rate of change of the link length.</li><li><strong>Bending.</strong> Our rope is perfectly flexible. Bending stiffness adds another constraint, for example on the distance between particles i and i + 2 or on the angle between neighboring links. Formula (5) is the same for it, with its own compliance.</li><li><strong>Collisions.</strong> Contact with an obstacle is an inequality constraint, handled the same way as a unilateral link (Sec. 5).</li></ul><h3>References</h3><ol><li>M. Macklin, M. Müller, N. Chentanez. <em>XPBD: Position-Based Simulation of Compliant Constrained Dynamics</em>. Motion in Games, 2016.</li><li>M. Macklin, K. Storey, M. Lu, P. Terdiman, N. Chentanez, S. Jeschke, M. Müller. <em>Small Steps in Physics Simulation</em>. SCA, 2019.</li><li>M. Müller, B. Heidelberger, M. Hennix, J. Ratcliff. <em>Position Based Dynamics</em>. VRIPHYS, 2006; J. Vis. Commun. Image Represent., 18(2), 2007.</li><li>J. Bender, M. Müller, M. Macklin. <em>Position-Based Simulation Methods in Computer Graphics</em>. Eurographics Tutorial, 2015.</li><li>M. Müller, M. Macklin, N. Chentanez, S. Jeschke, T.-Y. Kim. <em>Detailed Rigid Body Simulation with Extended Position Based Dynamics</em>. SCA, 2020.</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=79e6eb6a2f33" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Position Based Dynamics from Scratch: Simulating a Rope]]></title>
            <link>https://medium.com/@semen.tolstoguzov96/position-based-dynamics-from-scratch-simulating-a-rope-7d53b37a5921?source=rss-01347f1bf6b0------2</link>
            <guid isPermaLink="false">https://medium.com/p/7d53b37a5921</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[physics]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[game-development]]></category>
            <category><![CDATA[numerical-methods]]></category>
            <dc:creator><![CDATA[Simon]]></dc:creator>
            <pubDate>Fri, 13 Nov 2026 09:38:17 GMT</pubDate>
            <atom:updated>2026-11-13T09:38:17.287Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Deriving the method step by step, from constraints to a working algorithm</em></p><p>Position Based Dynamics (PBD) is a method for computing the motion of bodies: ropes, cloth, soft and rigid bodies. It was proposed by Müller et al. in 2006 [1], and since then it has been widely used in games and interactive graphics.</p><p>In ordinary dynamics, motion is driven by forces: accelerations are found from forces, and positions are obtained by integrating over time. In this approach, rigid constraints (an inextensible rope, a rigid body) have to be modeled with very stiff springs. Stiff springs require a very small time step, otherwise the simulation “blows up”.</p><p>PBD does without forces and works directly with positions. A body is represented as a set of particles, and the connections between them as geometric conditions on the particle positions, for example “the distance between two particles equals a given value”. At each time step, the particles first move by inertia, and then their positions are corrected so that the conditions hold again. The method does not give an exact solution of the equations of motion, but it is stable for any time step, simple, and fast.</p><p>To keep the presentation simple, we will study the method on a single problem: a rope with one end fixed at a stationary point and the other end moved by hand. It contains all the main parts of PBD, while the formulas stay short. First we state the problem (Sec. 1), then we build the method that solves it step by step.</p><h3>1. Problem</h3><p>A rope of length L is tied by one end to a fixed point A. The other end is held in a hand and moved around the plane in any way: left and right, up and down. The position of the hand at time t is denoted by the point B(t) =(x_B(t), y_B(t)). We need to find how the rest of the rope moves.</p><p>Assumptions:</p><ul><li>the rope is <strong>inextensible</strong> and perfectly flexible (it does not resist bending);</li><li>there are no external forces (gravity, wind), and the problem is planar.</li></ul><p>There is nothing around point A: it is just an attachment point, and the rope can freely pass on either side of it. All motion comes from the hand: it moves its end, and the rope passes this motion on from piece to piece.</p><p>Place the attachment point at the origin: A = (0, 0). The hand cannot move farther from point A than the length of the rope: |B(t) − A| ≤ L.</p><p>The method works for any hand motion. As a simple example we take the following: initially the rope is almost straight and lies along the x axis, then the hand moves toward point A and stops. The distance between the ends becomes smaller than the rope length, and the rope has to bend (Fig. 1).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lAnTRaE4QFoJMBILA5rU8A.png" /><figcaption><em>Fig. 1. A rope of length L: one end is fixed at point A, the other is held by the hand at point B(t). Gray shows the initial position, blue shows the rope after the hand has moved toward point A. The dashed line is the circle |B − A| = L, beyond which the hand cannot go.</em></figcaption></figure><h3>2. Solution idea</h3><p>Let us see what the general PBD scheme looks like for a rope. Inextensibility is specified not by springs but by a geometric condition: the distance between neighboring points of the rope equals a given value. One time step works as follows:</p><ol><li>each point of the rope takes a step <strong>by inertia</strong>, with its current velocity, as if it were not connected to anything; the ends are placed where they are supposed to be (point A and the hand);</li><li>the resulting “predicted” positions are <strong>shifted</strong> until all pieces of the rope have the right length again;</li><li>the velocity of each point is found after the fact: the difference between the new and old positions divided by the step.</li></ol><p>Next we go through it in order: how to describe the rope (Sec. 3), how to write the conditions (Sec. 4), what a time step looks like (Sec. 5), and how exactly to shift the points (Sec. 6, 7).</p><h3>3. Rope model</h3><h3>3.1 Particles</h3><p>We replace the rope with a chain of N particles numbered 1, …, N. Neighboring particles are connected by links. There is one link fewer than particles, i.e. N − 1, and the length of each is l₀ = L/(N − 1). Particle i has</p><ul><li>position <strong>r</strong>_i = (x_i, y_i),</li><li>velocity <strong>v</strong>_i,</li><li>inverse mass w_i = 1/m_i.</li></ul><p>The inverse mass is more convenient than the mass: in the PBD formulas mass enters precisely through w_i, and it makes the ends of the rope easy to describe.</p><h3>3.2 Rope ends</h3><p>The ends of the rope do not move on their own, but as they are told to:</p><ul><li>particle 1 is fixed: <strong>r</strong>₁ = A always;</li><li>particle N is in the hand: <strong>r</strong>_N = B(t).</li></ul><p>Such particles are given w = 0, i.e. infinite mass. We will see (Sec. 6) that a particle with w = 0 cannot be moved by links, so its position can be set externally. Such particles are called <strong>kinematic</strong>. Thus,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/855/1*bZz985DMX1rB5a1w6idDeA.png" /></figure><p>The value of w itself does not matter: only ratios of inverse masses appear in the formulas.</p><h3>3.3 Initial state</h3><p>At the initial moment the rope lies along the x axis with a slight bend and is at rest:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/978/1*QCW1LY7sMZrCXMjoK3b32Q.png" /></figure><p>where a is the bend amplitude.</p><p><strong>Why the bend is needed.</strong> If a = 0, all particles lie on the x axis. If the hand moves toward point A strictly along the x axis, as in our example, all links are horizontal, and all corrections will be horizontal too (Sec. 6.1). The rope will stay straight, and it will be impossible to fit it into the shortened segment. A small bend breaks the symmetry and determines which way the rope will buckle. If the hand also moves in y, the symmetry is broken by itself, and the bend is not necessary. The same happens if we include gravity directed across the rope (for example, along −y). Gravity pulls the inner particles down while the ends are fixed, so the rope sags, the links stop being horizontal, and the initial bend is not needed either.</p><p>Because of the bend, the links are initially slightly longer than l₀ (by hundredths of a percent for a = 0.01 L). This is not a problem: the method corrects the lengths on the very first step.</p><h3>4. Constraints</h3><p>The particles by themselves are not connected in any way: each would fly in a straight line with its own velocity. What makes them a rope are <strong>constraints</strong> — rules that the particle positions must obey. We have only one rule: neighboring particles are at distance l₀ from each other.</p><p>Such a rule is written as a numerical function C of the particle positions. The function is chosen so that it shows how much the rule is violated: C = 0 means the rule holds, and the larger |C|, the stronger the violation.</p><p>The positions substituted into C will be denoted <strong>p</strong>_i rather than <strong>r</strong>_i: constraints are checked and corrected for the <em>predicted</em> particle positions (Sec. 5).</p><p><strong>Link.</strong> For the link between particles i and i + 1 we take</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*95KTFVyXfeL6DUgV01JsGA.png" /></figure><p>If the particles are exactly l₀ apart, then C_i = 0. If the link is stretched to length 1.2 l₀, then C_i = 0.2 l₀ &gt; 0, and if it is compressed to 0.9 l₀, then C_i = −0.1 l₀ &lt; 0. The sign tells in which direction the rule is violated, the magnitude tells by how much.</p><p>The requirement for a link is the <strong>equality</strong> C_i = 0: both a stretched and a compressed link must be returned to length l₀.</p><p>In total, the rope is described by N − 1 constraints, one per link. All of them are hard: when corrected, the rule is satisfied fully, not partially as with a spring.</p><p>Together, the conditions C_i = 0 form a system of N − 1 equations in the coordinates of the inner particles. The equations are nonlinear: they contain the length of a vector. The problem is planar, each of the N − 2 inner particles has two coordinates, so there are 2(N − 2) unknowns — more than equations. In 3D there would be 3(N − 2) unknowns, and the gap would be even larger. Therefore there are infinitely many solutions: the rope can be laid out between its ends in different ways. We need a solution close to the predicted positions (Sec. 5). The original paper [1] proposes solving the system with a Gauss–Seidel-type iterative method: the equations are solved one at a time, each separately from the others, over several passes. Below we will see how to solve one equation (Sec. 6) and what happens when they are solved one after another (Sec. 7).</p><h3>5. Time step</h3><p>Suppose at time t the positions <strong>r</strong>_i and velocities <strong>v</strong>_i of all particles are known. The step to time t + Δt:</p><pre>(1) inner particles:  p_i ← r_i + Δt · v_i        // prediction by inertia<br>(2) ends:             p_1 ← A,  p_N ← B(t + Δt)   // prescribed motion<br>(3) repeat n_iter times:<br>        for each link: correct p                  // Sec. 6.1<br>(4) all particles:    v_i ← (p_i − r_i) / Δt      // new velocity<br>                      r_i ← p_i                   // new position</pre><p>How it works:</p><ul><li>If there were no constraints, step (4) would return the same velocity as before, and the particles would move uniformly in straight lines.</li><li>All the “physics” lives in step (3). It approximately solves the system from Sec. 4, taking the predicted positions as the initial guess. In doing so it shifts the predicted positions <strong>p</strong>_i, and step (4) turns this shift into a change of velocity. This is how the motion of the hand is passed along the links to the rest of the rope, even though not a single force is computed.</li><li>For the ends, step (4) gives the correct velocities by itself: for the fixed particle <strong>p</strong>₁ = <strong>r</strong>₁, and the velocity is zero; for the particle in the hand we get the average hand velocity over the step.</li></ul><p>It remains to understand how to solve the system in step (3).</p><h3>6. How to solve one equation</h3><h3>6.1 Link</h3><p>Take one equation of the system, C_i = 0, and solve it separately from the others.</p><p>Suppose that after the prediction the link between particles i and i + 1 has length d ≠ l₀. Denote</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/857/1*rWmkiaBENeIKUwkGoFgDoQ.png" /></figure><p>where <strong>n</strong> is the unit vector along the link, pointing from particle i + 1 to particle i. The length error is d − l₀.</p><p>To remove it, the particles have to be moved. Denote the displacements by Δ<strong>p</strong>_i and Δ<strong>p</strong>_(i+1). These are <strong>corrections</strong> — vectors added to the predicted positions of the particles:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/910/1*wZrdnxPOA8m7ROnIj3HRGQ.png" /></figure><p>On the right are the predicted positions <strong>p</strong>_i, <strong>p</strong>_(i+1), for which the link length is d. On the left are the corrected positions, for which the link length is exactly l₀. We find the corrections in three steps.</p><p><strong>Direction.</strong> A particle’s displacement can be split into two parts: along the link and across it. Only the part along the link changes the link length; the transverse part merely rotates the link. Therefore we move the particles only <strong>along the link</strong>, i.e. along <strong>n</strong>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/612/1*hympEYbt4DD0KZSlSEmbTg.png" /></figure><p>where a and b are as yet unknown numbers.</p><p><strong>Magnitude.</strong> The new link vector is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1005/1*T0X7iVPAixT4uRy25Mldvg.png" /></figure><p>so the new link length is d + a − b. It must become equal to l₀:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/332/1*WMetIaCtxLmtLN2sRxATig.png" /></figure><p>This is one equation in two unknowns. It says that together the particles must remove the whole error d − l₀, but it does not say how to split it between them.</p><p><strong>Shares.</strong> It is convenient to measure a and b as fractions of the error. Let particle i take on a share α of the error, and particle i + 1 a share β:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/770/1*xjA45zXXCry2FVKIMD5fqw.png" /></figure><p>that is,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1003/1*hYugDGI0ijmsVQLSjTqMhg.png" /></figure><p>Substituting a and b into the equation b − a = d − l₀ gives (α + β)(d − l₀) = d − l₀, that is,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/253/1*7auzOc80QlTdY7ADlRvENQ.png" /></figure><p><strong>Where the signs come from.</strong> The signs are chosen so that both shares are positive. The vector <strong>n</strong> points from particle i + 1 to particle i. Suppose the link is stretched: d − l₀ &gt; 0. The particles must be moved toward each other. Particle i must move toward particle i + 1, i.e. against <strong>n</strong>, so it gets a minus. Particle i + 1 must move toward particle i, i.e. along <strong>n</strong>, so it gets a plus. If the link is compressed, then d − l₀ &lt; 0, the factor changes sign by itself, and the same formulas push the particles apart. The signs depend on how the direction of <strong>d</strong> is chosen: if we take <strong>d</strong> = <strong>p</strong>_(i+1) − <strong>p</strong>_i, they swap places, while the displacements themselves stay the same.</p><p><strong>How to split the error.</strong> The condition α + β = 1 leaves freedom: the error can be split between the particles in any way. To choose the shares, we require that the correction does not move the link’s center of mass:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/568/1*857shlCTCWoLfoA4KfI7lA.png" /></figure><p>Then the correction adds no momentum to the rope: the link does not push itself. Substituting the corrections here and cancelling (d − l₀)<strong>n</strong>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Q0k9BDYigiUxJDesdALjFw.png" /></figure><p>A particle’s share is inversely proportional to its mass, i.e. proportional to its inverse mass w: a light particle moves more than a heavy one. Together with the condition α + β = 1 we get</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/767/1*UswKWYqsI5056WrfMQ_Faw.png" /></figure><p><strong>Why inverse masses rather than masses.</strong> The same shares can be written in terms of masses: α = m_(i+1)/(m_i + m_(i+1)), β = m_i/(m_i + m_(i+1)). But the form with w is more convenient:</p><ul><li>a fixed particle has infinite mass, and the mass formula gives ∞/∞, whereas with inverse masses it is simply w = 0: the share is zero, and the particle does not move;</li><li>with masses, a particle’s share is expressed through the mass of its neighbor, whereas with w the rule is simpler: each particle’s displacement is proportional to its own w;</li><li>this rule carries over unchanged to constraints with any number of particles (Sec. 6.2).</li></ul><p>The meaning of the inverse mass is simple: it shows how easy it is to move a particle. The link acts on both particles with equal and opposite forces, and the same force F gives a particle the acceleration F/m = wF.</p><p><strong>Corrections for a link:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QufvL5cU8l4jUPWOqmSyAw.png" /></figure><p>For our rope there are three cases:</p><ul><li>an inner link, both particles free — each moves by half the error;</li><li>the first link (i = 1): w₁ = 0, the fixed particle does not move, and <strong>p</strong>₂ takes the whole error;</li><li>the last link (i = N − 1): w_N = 0, the hand does not yield, and <strong>p</strong>_(N−1) takes the whole error.</li></ul><p>After the correction the link length is exactly l₀. But correcting link i moves particles that also belong to the neighboring links i − 1 and i + 1, and spoils their lengths. What to do about this is covered in Sec. 7.</p><p>In code it is more convenient not to normalize <strong>d</strong> separately, but to take c = (d − l₀)/(d·(w_i + w_(i+1))) and move the particles by ∓w·c·<strong>d</strong> — this is the same thing.</p><h3>6.2 General formula</h3><p>We guessed the corrections for a link from geometry. PBD has a general formula that gives the correction for any constraint C, and our corrections follow from it. It will be useful if you want to add other constraints, for example on the angle between links or on collision with an obstacle.</p><p>Suppose the constraint involves particles <strong>p</strong>₁, …, <strong>p</strong>_n and C(<strong>p</strong>) ≠ 0. We look for corrections Δ<strong>p</strong>_i after which C = 0.</p><p><strong>Linearization.</strong> As in Newton’s method, we replace the equation with a linear one. To do this, we expand C in a Taylor series around the current positions <strong>p</strong>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*AhZhDjQFKMT8aXGmqn-j9Q.png" /></figure><p>where the gradients are evaluated at <strong>p</strong>. The first two terms are the function value and its linear part. The remainder is of second order in the corrections, and for small corrections we discard it. What remains we set to zero:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/830/1*X_oqbabNYkOsdidckUMc2w.png" /></figure><p>Because of the discarded remainder, the corrections found from this equation in general make C vanish only approximately. For a link the result is exact (see “Check on a link” below).</p><p>This is one equation in many unknowns; there are infinitely many solutions, and we need to pick one.</p><p><strong>Choosing a solution.</strong> Among all solutions we take the one that moves the particles the least. The predicted positions are motion by inertia, i.e. what the particles would do without constraints, and a constraint should change this no more than necessary. We measure the amount of displacement by a mass-weighted sum, so that moving a heavy particle “costs” more than moving a light one:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rJUZuuPJPU6DQ5Y0R9EPAg.png" /></figure><p>The factor ½ does not affect the location of the minimum; it is only there so that the two cancels upon differentiation. This measure has a physical basis — Gauss’s principle of least constraint: the actual motion of a constrained system minimizes the sum Σᵢ m_i·|<strong>a</strong>_i − <strong>a</strong>_i^free|², where <strong>a</strong>_i^free is the particle’s acceleration without constraints. The correction Δ<strong>p</strong>_i is the deviation from free motion over the step; it is proportional to (<strong>a</strong>_i − <strong>a</strong>_i^free)·Δt², so our sum is the same quantity written in terms of positions.</p><p>The condition here is the linearized equation (1). This is a constrained minimization problem, solved by the method of Lagrange multipliers. We form the function</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ujeOVSjSB9m3DnoZPPX-cg.png" /></figure><p>and set its derivative with respect to each correction Δ<strong>p</strong>_i to zero:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/483/1*2cU4AiCq6eHYHIMG5wSQ9g.png" /></figure><p>Dividing by m_i, we get</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/644/1*xUIzcG-2YKzVukn1omDfIw.png" /></figure><p>Each particle moves along the gradient of C with respect to its position (the direction in which C changes fastest), and the size of the displacement is proportional to the inverse mass. The number λ is the Lagrange multiplier; it is common to all particles of the constraint. A kinematic particle (w_i = 0) does not move.</p><p>This choice conserves momentum. If C depends only on the relative arrangement of the particles and does not change when they are all translated as a whole, then Σᵢ ∇_(<strong>p</strong>_i) C = 0, and then</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/634/1*Ky0feE9O_OFt7D29CHa9eg.png" /></figure><p>This is the same condition of a stationary center of mass from which the shares α and β were obtained in Sec. 6.1.</p><p><strong>Multiplier.</strong> Formula (2) has one remaining unknown number, λ. To find it, we substitute the corrections (2) into the linearized equation (1):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/747/1*MgNt0IVLqNhuFb9G_O1KoA.png" /></figure><p>The dot product of the gradient with itself is the square of its length, and λ comes out of the sum:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/603/1*9Vi9YkMxqu48fnLfKI58Tg.png" /></figure><p>Hence</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/729/1*Ypg4rlF9l69y54u6kK_2-g.png" /></figure><p>The summation index here is named j to avoid confusion with the particle index i in formula (2).</p><p><strong>Result.</strong> Substituting λ from (3) into formula (2):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/748/1*pPOX1tX2MnzcPcYLuKsFZQ.png" /></figure><p>If the denominator is zero (all particles of the constraint are kinematic), the constraint is skipped. An inequality C ≥ 0 is corrected only if it is violated.</p><p><strong>Check on a link.</strong> For C = |<strong>p</strong>_i − <strong>p</strong>_(i+1)| − l₀ the gradients are ∇_(<strong>p</strong>_i) C = <strong>n</strong> and ∇_(<strong>p</strong>_(i+1)) C = −<strong>n</strong>, their lengths are one, and the denominator is w_i + w_(i+1). We get exactly the corrections from Sec. 6.1.</p><h3>7. All constraints together</h3><h3>7.1 Correcting one at a time</h3><p>Correcting a single link is easy, but the links depend on each other: each inner particle belongs to two links, and correcting one spoils its neighbors. Solving the whole system jointly is expensive, so PBD uses the Gauss–Seidel-type method mentioned in Sec. 4: it corrects the constraints <strong>one at a time</strong>, one after another. Each correction immediately changes <strong>p</strong>, and the next constraint sees the already corrected positions. One pass over all constraints is one iteration. n_iter passes are made. With each iteration the violations decrease, but all constraints cannot be satisfied exactly in a finite number of iterations.</p><p>This is a nonlinear variant of the Gauss–Seidel method. It also differs from the classical one in that there the i-th equation is solved for one unknown, the i-th, whereas here it is solved for all coordinates of both particles of the link (Sec. 6.1). The iterations start from the predicted positions, and each correction moves the particles as little as possible, so the solution found stays close to the predicted positions.</p><p><strong>When to stop.</strong> Iterative methods are usually stopped by a convergence criterion. In PBD it is traditional to simply set the number of passes n_iter, and there are three reasons for this:</p><ul><li>the step time is predictable: the method was designed for games, where a frame has a limited time budget, and reaching a given accuracy may take 20 passes one time and 2000 another;</li><li>an exact solution is not required: stability does not depend on convergence, the residual error shows up as slight stretchiness (Sec. 7.2), and the next step continues correcting the same positions;</li><li>the loop always terminates: if the hand has moved farther than L from point A, the system has no solution, and a convergence criterion would never be met.</li></ul><p>Both approaches can be combined: exit the loop early if the largest relative link length error over a pass is less than a given ε,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/326/1*NPMn23kc8zQHZyoPxopxiA.png" /></figure><p>but make no more than n_iter passes. The check costs almost nothing: |C_i| is computed anyway while traversing the links.</p><h3>7.2 Traversal order and apparent stretchiness</h3><p>Suppose the links are traversed from the attachment point to the hand (i = 1, 2, …, N − 1), and the hand has moved toward point A by δ over the step. Right after the prediction, only the last link is violated: it has become shorter. In the first iteration, correcting it moves particle N − 1, and link N − 2 becomes violated. But its turn in this iteration has already passed, and it will be corrected only in the next one. Thus the hand’s displacement propagates toward the attachment point by only one link per iteration. This is how the slow convergence of the Gauss–Seidel method on long chains shows up.</p><p>If n_iter ≪ N, the displacement does not even reach the middle of the rope: the links near the hand remain shortened, and the rope looks compressible (and if the hand moves away from point A, stretchable), even though all constraints are hard. This is not a property of the rope but a numerical error. It is larger the smaller n_iter is and the larger the hand displacement per step δ = |B(t + Δt) − B(t)| is compared to l₀.</p><p>What helps:</p><ul><li>increase n_iter (on the order of N or more); for example, n_iter = 200 for N = 50;</li><li>move the hand more slowly or decrease Δt;</li><li>alternate the traversal direction: on even iterations from the attachment point to the hand, on odd ones back;</li><li>add “long-range” constraints (<em>long range attachments</em>, Kim et al., 2012): particle i may be no farther than (i − 1) l₀ from point A and no farther than (N − i) l₀ from the hand,</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/992/1*zyjCN8gpSvdE88nUfq8sRw.png" /></figure><p>Each such constraint immediately limits the stretching of a whole piece of the rope rather than of a single link.</p><h3>8. Complete algorithm</h3><p>Putting it all together. The step numbering is the same as in Sec. 5.</p><pre>given: r(1..N), v(1..N), w(1..N) with w(1) = w(N) = 0,<br>       attachment point A, hand motion law B(t), l0, Δt, n_iter, ε<br><br>p(i) ← r(i) + Δt · v(i)  for i = 2..N−1          // (1) prediction by inertia<br>p(1) ← A                                         // (2) ends<br>p(N) ← B(t + Δt)<br><br>repeat at most n_iter times:                     // (3) constraint correction<br>    err ← 0                                      //     largest error in the pass<br>    for i = 1..N−1:                              //     links, from point A to the hand<br>        d  ← p(i) − p(i+1)<br>        dl ← |d|<br>        err ← max(err, |dl − l0|)<br>        ws ← w(i) + w(i+1)<br>        if ws = 0 or dl = 0: skip<br>        c  ← (dl − l0) / (dl · ws)<br>        p(i)   ← p(i)   − w(i)   · c · d<br>        p(i+1) ← p(i+1) + w(i+1) · c · d<br>    if err &lt; ε · l0: exit loop                   //     converged early (Sec. 7.1)<br><br>for i = 1..N:                                    // (4) velocities and positions<br>    v(i) ← (p(i) − r(i)) / Δt<br>    r(i) ← p(i)</pre><p>The law B(t) can be anything; only the hand position at the end of the step, B(t + Δt), enters the algorithm. In our example the hand moves toward point A along the x axis: for the first n_push steps B(t + Δt) = B(t) − (δ, 0), then the hand stays still.</p><p>The code for this example is on GitHub: <a href="https://github.com/Semen1996/pbd-method-rope">github.com/Semen1996/pbd-method-rope</a>.</p><h3>9. What’s next</h3><p>We did not consider gravity, elastic (compliant) constraints, or tension forces, including the force with which the rope pulls the hand. Compliant constraints and forces are described by XPBD (Macklin, Müller, Chentanez, 2016). The slow convergence on long chains is cured by the <em>small steps</em> variant (Macklin et al., 2019): the step Δt is split into substeps with one iteration in each.</p><h3>References</h3><ol><li>M. Müller, B. Heidelberger, M. Hennix, J. Ratcliff. <em>Position Based Dynamics</em>. VRIPHYS, 2006; J. Vis. Commun. Image Represent., 18(2), 2007.</li><li>J. Bender, M. Müller, M. Macklin. <em>Position-Based Simulation Methods in Computer Graphics</em>. Eurographics Tutorial, 2015.</li><li>T. Kim, N. Chentanez, M. Müller-Fischer. <em>Long Range Attachments — A Method to Simulate Inextensible Clothing in Computer Games</em>. SCA, 2012.</li><li>M. Macklin, M. Müller, N. Chentanez. <em>XPBD: Position-Based Simulation of Compliant Constrained Dynamics</em>. Motion in Games, 2016.</li><li>M. Macklin, K. Storey, M. Lu, P. Terdiman, N. Chentanez, S. Jeschke, M. Müller. <em>Small Steps in Physics Simulation</em>. SCA, 2019.</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7d53b37a5921" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Simulating Fluid Flow with the SIMPLE Method]]></title>
            <link>https://medium.com/@semen.tolstoguzov96/simulating-fluid-flow-with-the-simple-method-398c40da9ac4?source=rss-01347f1bf6b0------2</link>
            <guid isPermaLink="false">https://medium.com/p/398c40da9ac4</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[cfd]]></category>
            <category><![CDATA[fluid-dynamics]]></category>
            <category><![CDATA[numerical-methods]]></category>
            <category><![CDATA[physics]]></category>
            <dc:creator><![CDATA[Simon]]></dc:creator>
            <pubDate>Sun, 01 Nov 2026 16:40:41 GMT</pubDate>
            <atom:updated>2026-11-01T16:40:41.981Z</atom:updated>
            <content:encoded><![CDATA[<p>This article describes the SIMPLE method (Semi-Implicit Method for Pressure-Linked Equations). The method was proposed by S. Patankar and D. Spalding in 1972 [2]. The article covers the governing equations, control volume discretization, the staggered grid, the SIMPLE algorithm itself, boundary conditions, solving the linear systems, and under-relaxation. At the end there is a link to a test program in Octave that computes the flow in a lid-driven cavity. The presentation follows S. Patankar’s book <em>Numerical Heat Transfer and Fluid Flow</em> [1] (hereafter “Patankar”), Chapters 2–6. Where we depart from the book, this is stated explicitly.</p><p>For comparison, the article on Chorin’s projection method [8] is useful, but you do not need to know it.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/542/1*N-_SAE7oZ3iCVXu9vzIKNA.png" /></figure><h3>1. Equations</h3><p>The flow of a viscous incompressible fluid is described by the Navier–Stokes equations:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/243/1*wPdrdzevoa9PVK94S76w-w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/764/1*WTqQu7rFVjSH9W_uAtHkrw.png" /></figure><p>where <strong>u</strong> = (u, v) is the velocity, p is the pressure, ρ is the density, and μ is the dynamic viscosity (the kinematic viscosity is ν = μ/ρ). There are no body forces. Bold <strong>u</strong> denotes the velocity vector, plain u its x-component. Patankar writes the equations in terms of μ rather than ν, and we follow him.</p><p><strong>Conservative form.</strong> Because the fluid is incompressible, the convective term can be moved under the derivative: u·∂u/∂x + v·∂u/∂y = ∂(uu)/∂x + ∂(vu)/∂y. The difference between the two forms is u·(∂u/∂x + ∂v/∂y) = 0. We obtain a system of three scalar equations for the three unknowns u, v, p:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/455/1*pmjJHwFlofZzfTzM7DHFkw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*TUj5Zs7a2JNbCd1sZGbggw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8z4iuqV6BujRVyXNGC51LA.png" /></figure><p>The conservative (divergence) form is convenient because every term is a derivative of a flux. This is the form the control volume method works with (Section 2).</p><h3>1.1. The general transport equation</h3><p>The central idea of Patankar’s book is that the equations of motion, heat conduction, species diffusion and many others all have the same form</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/849/1*JbQkvdhGiE5krmJgM-6fFQ.png" /></figure><p>where φ is the transported quantity, Γ is the diffusion coefficient, and S is the source.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1002/1*IFyLYxvmJpYtzaqygItd-Q.png" /></figure><p>So it is enough to learn once how to discretize the general equation (Section 2), and the same procedure works for all the equations at once. Only the pressure needs special attention.</p><h3>1.2. The pressure problem</h3><p>Pressure has no equation of its own. The momentum equations contain p, but they serve to determine u and v. The continuity equation, the only one left, does not contain p at all. Pressure is defined indirectly: it is the field which, when substituted into the momentum equations, yields a velocity that satisfies continuity.</p><p>This gives two ways to find the pressure:</p><ul><li><strong>Chorin’s method</strong> [8]: at every time step, a Poisson equation for pressure is solved that makes the velocity divergence-free.</li><li><strong>The SIMPLE method</strong>: the pressure is guessed and then iteratively corrected according to how badly continuity is violated.</li></ul><p>In addition, the equations are nonlinear: the coefficients of the discrete momentum equations depend on the velocity itself. So for a steady problem iterations are needed anyway, and SIMPLE resolves the nonlinearity and the pressure in a single iteration loop.</p><p>Before turning to the SIMPLE algorithm itself (Section 4), we need to learn how to write the equations in discrete form (Section 2) and decide at which grid points to store velocity and pressure (Section 3).</p><h3>2. Spatial discretization</h3><h3>2.1. The control volume method</h3><p>Write the steady general equation (Section 1.1) in terms of the flux <strong>J</strong>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/701/1*ycOuZTabsxXr7eBbPe5P-Q.png" /></figure><p>The flux <strong>J</strong> consists of a convective part (the moving fluid carries φ along) and a diffusive part (φ spreads from where there is more of it to where there is less). Divide the domain into control volumes (CVs) and integrate the equation over the CV around node P. We use Patankar’s notation: nodes are denoted by capital letters P (current), E, W, N, S (east, west, north and south neighbours), and the CV faces between them by lowercase e, w, n, s. The problem is two-dimensional, so all quantities are per unit depth: the area of face e is A_e = Δy · 1.</p><pre>N<br>                                 *<br>                                 :<br>   ---               +-----------n-----------+<br>    ^                |                       |<br>    |                |                       |<br>    |      W         |           P           |         E<br> Δy |      *.........w...........*...........e.........*<br>    |                |                       |<br>    |                |                       |<br>    v                |                       |<br>   ---               +-----------s-----------+<br>                                 :<br>                                 *<br>                                 S<br><br>           |&lt;------ δx_w -------&gt;|&lt;------ δx_e -------&gt;|<br>                     |&lt;-------- Δx ---------&gt;|</pre><p>Asterisks are nodes; the rectangle is the CV of node P, of size Δx × Δy. The CV faces lie between nodes; δx_e and δx_w are the distances from P to the neighbours E and W (on a uniform grid they equal Δx).</p><p>By the divergence (Gauss) theorem, the volume integral of a divergence equals the flux through the boundary. For a rectangular CV with faces e, w, n, s:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/997/1*ib9Xz5LzxQa-0AySSAkNyw.png" /></figure><p>where J_e is the x-component of the flux at face e, J_n the y-component at face n, and ΔV = Δx·Δy. This is a <strong>balance equation</strong>: outflow through the faces minus inflow equals what is generated inside. The flux through a face shared by two neighbouring CVs enters their equations with opposite signs, so summing the equations of all CVs gives an exact balance for the whole domain. The scheme is <strong>conservative</strong>: neither mass nor momentum is created or destroyed inside the domain by discretization errors.</p><p>What remains is to express the face fluxes through nodal values. Whatever method is used, the result is written as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MsEe0PsZMLXopDdArWeCfA.png" /></figure><p>Patankar (Ch. 3–4) formulates <strong>four basic rules</strong> that a discretization must satisfy to give physically realistic results:</p><ol><li><strong>Consistency at control volume faces.</strong> The flux through a shared face must be computed by the same expression for both adjacent CVs. Otherwise conservation is violated.</li><li><strong>Positive coefficients.</strong> All a_nb and a_P must be positive. An increase of φ at a neighbouring node, all else being equal, must raise φ_P, not lower it.</li><li><strong>Negative-slope source linearization.</strong> If the source depends on φ, it is written as S = S_C + S_P·φ_P with S_P ≤ 0.</li><li><strong>Sum of the neighbour coefficients.</strong> In the absence of a source, a_P = Σ a_nb: if all neighbours have the same value of φ, then φ_P must have that value too.</li></ol><h3>2.2. Diffusion</h3><p>The diffusive flux through face e is approximated by the difference of the values at the adjacent nodes:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*syA0b0Mdd5a_bqzQZweIqA.png" /></figure><p>where δx_e is the distance between nodes P and E. It is convenient to think of D_e as the “conductance” of the face: the larger it is, the more strongly the nodes are coupled. Without convection we would get a_E = D_e, a_W = D_w, a_N = D_n, a_S = D_s.</p><h3>2.3. Convection and diffusion: choosing a scheme</h3><p>The convective flux through face e is F_e·φ_e, where</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/319/1*C9vyMkdyUGQWuL6x_arvIw.png" /></figure><p>is the <strong>mass flow rate</strong> through the face. A new difficulty appears here: we need the value φ_e at the face, but only nodal values are known. The ratio of convection to diffusion at a face is characterized by the <strong>grid Péclet number</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/473/1*5m97DzLcd3O_MhIndhkX2A.png" /></figure><p>For the momentum equations Γ = μ, and the Péclet number coincides with the grid Reynolds number ρu·δx/μ.</p><p><strong>Central differencing.</strong> The natural choice is the average: φ_e = (φ_P + φ_E)/2. Then</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/688/1*bMYPbI2k8hLzWJXeuaZBUg.png" /></figure><p>For P_e &gt; 2 the coefficient becomes negative, and rule 2 is violated. In practice this produces unphysical sawtooth oscillations in the solution and divergence of the iterations.</p><p><strong>The upwind scheme.</strong> The face value is taken from the upstream node: φ_e = φ_P if F_e &gt; 0 and φ_e = φ_E if F_e &lt; 0. Then</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/528/1*sLIJemLObNOsCogWidKxHg.png" /></figure><p>is always positive. The price is first-order accuracy and <strong>numerical (false) diffusion</strong>: when the flow is oblique to the grid lines, the scheme smears the solution as if the viscosity were larger than it really is.</p><p><strong>The exact solution and the power-law scheme.</strong> Patankar (Ch. 5) derives a scheme from the exact solution of the one-dimensional steady convection–diffusion equation. Between two nodes the solution has an exponential profile:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/659/1*cQTSVOmMkst9RcmNW3j4XQ.png" /></figure><p>As |P| → 0 the profile is linear (pure diffusion; central differencing is correct). For large |P| the profile is nearly constant and equal to the upstream value, changing sharply only near the downstream node: the face value is close to the upwind value, and diffusion is almost switched off. The exponential scheme is exact for the one-dimensional problem, but the exponential is expensive to compute. Patankar proposes a cheap and very accurate approximation of it, the <strong>power-law scheme</strong>.</p><p><strong>The general formula.</strong> All of these schemes fit into a single expression:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*bzsUQhW6Mu6K5YKgIhewRA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/890/1*kCBCq-y9ujQJyUH25jTSmA.png" /></figure><p>where the scheme is determined by the function A(|P|):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cTE2ivB_4B33mulxTWGbaw.png" /></figure><p>The first term in (2.3) is diffusion, damped when convection is strong; the second is convection, which carries information only downstream.</p><p><strong>A note on a_P.</strong> Strictly speaking, integration gives a_P = Σ a_nb + (F_e − F_w + F_n − F_s). The last bracket is the mass balance of the CV, which is zero for a field that satisfies continuity. Patankar drops it right away. This way rule 4 holds exactly, and diagonal dominance a_P ≥ Σ a_nb is preserved during intermediate iterations. We do the same.</p><h3>3. The staggered grid</h3><h3>3.1. Checkerboard pressure</h3><p>Why not store u, v and p at the same points? Patankar (Ch. 6) shows that such a (collocated) grid hides a trap. The pressure gradient at node P computed by a central difference,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/473/1*vwJHrYbot6XIVxs5YYwy5g.png" /></figure><p>does not contain p_P. Take a “checkerboard” pressure field: along a grid line the values alternate 100, 300, 100, 300, … At every node p_E = p_W, and the difference is zero. The momentum equation “sees” this highly non-uniform field as a constant one. If such a field satisfies the equations, then so does the solution with any checkerboard field added to it, and the numerical solution may contain unphysical sawtooth pressure oscillations.</p><p>The same happens with continuity: the difference u_E − u_W is zero for a zigzag velocity 1, 7, 1, 7, …</p><h3>3.2. The staggered (MAC) grid</h3><p>The remedy is to store the velocity components on the faces of the pressure cells (Harlow &amp; Welch, 1965 [3]):</p><ul><li>p at the cell centre;</li><li>u at the centres of the vertical (left/right) faces;</li><li>v at the centres of the horizontal (bottom/top) faces.</li></ul><pre>v(i-1,j+1)              v(i,j+1)<br>     +-----------o-----------+-----------o-----------+<br>     |           :           |           :           |<br>     |           :           |           :           |<br>     o           *           o           *           o<br> u(i-1,j)    p(i-1,j)      u(i,j)      p(i,j)     u(i+1,j)<br>     |           :           |           :           |<br>     |           :           |           :           |<br>     +-----------o-----------+-----------o-----------+<br>              v(i-1,j)                v(i,j)</pre><p>Now the pressure difference p_P − p_E between neighbouring cells falls exactly on the face where the velocity u_e lives, and the difference of the face fluxes of a cell gives its divergence without interpolation. A checkerboard pressure produces a difference of ±200 on every face and is immediately “noticed” by the momentum equation.</p><p><strong>Three kinds of control volumes.</strong> Each equation is integrated over its own CV:</p><ul><li>the continuity equation (and, in Section 4, the pressure-correction equation for p’) over the pressure cell (solid lines in the figure);</li><li>the equation for u(i,j) over a CV shifted by half a cell in x. In the figure it is the rectangle between the dotted lines: its faces pass through the nodes p(i−1,j) and p(i,j), and its corners through the v nodes;</li><li>the equation for v(i,j) over a CV shifted by half a cell in y.</li></ul><p>The pressure force on the CV of velocity u(i,j) is the difference p(i−1,j) − p(i,j) between its faces times the face area Δy. No pressure interpolation is needed.</p><p><strong>Alternative.</strong> On a collocated grid, checkerboard oscillations are suppressed by a special interpolation of the velocity to the faces (Rhie &amp; Chow, 1983 [6]). This is how most industrial codes for unstructured grids work. This article uses a staggered grid, as Patankar does.</p><h3>3.3. Array storage</h3><p>The L × H domain is divided into n_x × n_y equal cells with spacings Δx = L/n_x, Δy = H/n_y. The first array index corresponds to x, the second to y:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hKrI_8j7uTywVigaTfBzTw.png" /></figure><p>The unknowns are u(2:nx, :) and v(:, 2:ny). The elements on the walls hold the prescribed values of the normal velocity. There are no ghost nodes outside the boundary: the conditions for the tangential velocity are built directly into the coefficients (Section 5.1).</p><h3>3.4. Momentum equations on the staggered grid</h3><p><strong>Equation for u(i,j)</strong>, i = 2, …, n_x, j = 1, …, n_y. Its CV spans, in x, the interval between the centres of cells i−1 and i, and in y the row of cells j. The mass flow rates through the CV faces are computed by interpolating the velocity from neighbouring nodes:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fXESPCoBaIXFJ4oYQKbVpw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xxkswgZ5dlNhkIz40SKDiQ.png" /></figure><p>Face conductances:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/882/1*ZibV-cq9uwRXUwmdxk3IVA.png" /></figure><p>The coefficients are computed from (2.3), the neighbours are the nodes u_(i±1, j), u_(i, j±1), and the pressure term is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/691/1*n65YFn28Mg1CfGX2OAAxKw.png" /></figure><p><strong>Equation for v(i,j)</strong>, i = 1, …, n_x, j = 2, …, n_y, is symmetric:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MOJl01SLQZEWEsv1PhLW9g.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Aiw9z2qF_nl_shqI2kVf5A.png" /></figure><p>with the pressure term (p_(i, j−1) − p_(i, j))·Δx.</p><p><strong>Nonlinearity.</strong> The flow rates F depend on the very velocity we are solving for. They are computed from the velocity of the previous iteration and treated as known. The equations become linear, and the nonlinearity is resolved by the outer SIMPLE iterations, the same ones that refine the pressure.</p><h3>4. The SIMPLE algorithm</h3><p>SIMPLE works on a “guess and correct” principle:</p><ol><li><strong>Guess the pressure</strong> p*.</li><li><strong>Solve the momentum equations with this pressure.</strong> This gives the velocity <strong>u</strong>* = (u*, v*). Since the pressure guess is wrong, <strong>u</strong>* does not satisfy continuity: some cells receive more inflow than outflow, others less.</li><li><strong>Correct the pressure and velocity.</strong> Find a pressure correction p’ such that the corrected velocity satisfies continuity. Where fluid has “accumulated”, the pressure rises and pushes the excess out to the neighbours.</li><li><strong>Repeat</strong> until the fields stop changing.</li></ol><h3>4.1. Discrete equations</h3><p>The momentum equations for the staggered-grid nodes are written in Section 3.4. For deriving SIMPLE, the specific form of the coefficients does not matter; only the structure does. We write the equations in the notation of Section 2.1: the velocity u_e is stored on face e between pressure nodes P and E, and the face area is A_e = Δy.</p><p><strong>Momentum equation</strong> for node u_e:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/985/1*zpvN7kUfNjKU9I7QZsk62w.png" /></figure><ul><li>a_e is the coefficient showing how strongly the velocity at the node is coupled to its neighbours;</li><li>Σ a_nb·u_nb is the influence of the neighbouring velocity nodes (subscript nb for neighbour) through convection and diffusion;</li><li>b contains other sources and known boundary values;</li><li>(p_P − p_E)·A_e is the pressure force acting on the control volume: the pressure difference times the face area.</li></ul><p>Similarly for v_n:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/994/1*-jQO_N0NQBekhpwS5jejug.png" /></figure><p><strong>Continuity equation</strong> for cell P (constant-density fluid): as much mass must flow out through the cell faces as flows in:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/954/1*vGRTOHgI8MCk9ybeDp0PQw.png" /></figure><h3>4.2. Pressure and velocity corrections</h3><p>Write the sought fields as the guessed ones plus corrections:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/937/1*snfdbHeEhBekNOe7YzARuQ.png" /></figure><p>The velocity u* is obtained from equation (4.1) with pressure p*:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/795/1*DLJPZzN6RIgXMMWcgY_8DQ.png" /></figure><p>Subtract this from (4.1). The term b cancels:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/910/1*ceGaM6I-ocF8sc6qMN0leQ.png" /></figure><p>The velocity correction at a node depends on the nearby pressure corrections and on the velocity corrections at all neighbouring nodes. These in turn depend on their neighbours, and so on across the whole domain. <strong>The key simplification of SIMPLE: the term Σ a_nb·u’_nb is dropped.</strong> Then</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/913/1*phb1hN9-PXDZjvQsWj52nQ.png" /></figure><p>and the corrected velocity is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*e3urLLLLytCrdyiDBzEDEQ.png" /></figure><p>Hence the name of the method: the velocity correction implicitly accounts only for the pressure-correction difference across “its own” face, while the influence of neighbouring velocities is omitted. The method is “semi-implicit”.</p><p><strong>Why this is allowed.</strong> The simplification changes only the path to the solution, not the solution itself. At convergence the guessed pressure becomes correct, p’ = 0, u’ = 0, and the dropped term is zero as well. The converged solution satisfies the original equations (4.1)–(4.3) without any simplifications. The price of the simplification is that the correction p’ comes out too large and has to be damped by under-relaxation (Section 7).</p><h3>4.3. The pressure-correction equation</h3><p>Substitute the corrected velocities (4.6) into the continuity equation (4.3) and collect the terms with p’:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZlslcRSAP7a_GHObKULMmQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rIopxAWDDB5PcxXDjQQ1zw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/762/1*aiIWsddU8Jc6QAh4UE_Jug.png" /></figure><p>The right-hand side b is the <strong>mass imbalance</strong> of the cell for the field <strong>u</strong>*: how much more mass flows into the cell than out of it. The meaning of the equation is clear:</p><ul><li>if b &gt; 0 (fluid accumulates in the cell), the correction p’_P comes out larger than at the neighbours, and the corrected velocities (4.6) point out of the cell;</li><li>if b = 0 in every cell, then p’ = 0: the field <strong>u</strong>* already satisfies continuity. So the total imbalance b serves as one of the convergence indicators; in addition, the residuals of the momentum equations must also be small (Section 7.6).</li></ul><h3>4.4. The pressure-correction equation in index form</h3><p>For cell (i, j), equation (4.7) becomes</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zTZq5orXNgDB2nfjBtHvwQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/951/1*gD-h9LRX-ch4GLgqg5ffew.png" /></figure><p>where dᵘ_(i,j) = Δy / aᵘ_(i,j) is the coefficient d for node u(i,j) and aᵘ_(i,j) is the diagonal coefficient of its momentum equation (similarly for dᵛ). The velocity correction is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cty0LP_eXNG5riN2Hoie4A.png" /></figure><p>Note the symmetry: the coefficient a_E of cell (i,j) equals the coefficient a_W of cell (i+1,j). The matrix of the system for p’ is symmetric (Section 6).</p><h3>4.5. Sequence of operations</h3><p>The SIMPLE algorithm according to Patankar (Ch. 6):</p><ol><li>Set an initial pressure field p* (and an initial velocity field, from which the coefficients are computed).</li><li>Solve the momentum equations (4.1), (4.2) with pressure p* to get u*, v*.</li><li>Solve the pressure-correction equation (4.7) to get p’.</li><li>Correct the pressure: p = p* + p’ (with under-relaxation: p = p* + α_p·p’, Section 7).</li><li>Correct the velocity using (4.6).</li><li>Solve the equations for other quantities φ (temperature, concentration) if they affect the flow (not the case in our problem).</li><li>Take p as the new p*, recompute the coefficients from the new velocity and return to step 2. Repeat until the residuals are small.</li></ol><pre>┌────────────────────────────────┐<br>            │  initial u, v, p*              │<br>            └───────────────┬────────────────┘<br>                            ▼<br>   ┌──────────────────────────────────────────────────┐<br>   │ 2. coefficients a from current velocity;         │◄────────┐<br>   │    momentum equations with p*  →  u*, v*         │         │<br>   └───────────────┬──────────────────────────────────┘         │<br>                   ▼                                            │<br>   ┌──────────────────────────────────────────────────┐         │<br>   │ 3. p&#39; equation (RHS = mass imbalance             │         │<br>   │    of u*, v*)  →  p&#39;                             │         │<br>   └───────────────┬──────────────────────────────────┘         │<br>                   ▼                                            │<br>   ┌──────────────────────────────────────────────────┐         │<br>   │ 4–5. p = p* + αp·p&#39;;   u = u* + d·Δp&#39;            │         │<br>   └───────────────┬──────────────────────────────────┘         │<br>                   ▼                                            │<br>            residuals small? ── no ──── p* := p ────────────────┘<br>                   │<br>                  yes<br>                   ▼<br>                  end</pre><h3>5. Boundary conditions</h3><h3>5.1. Velocity</h3><p>The domain boundary runs along the faces of the pressure cells. On each side, one velocity component is <strong>normal</strong> to the boundary and the other is <strong>tangential</strong>, and their nodes are located differently.</p><ul><li><strong>Normal component.</strong> The nodes lie right on the boundary (u(1,:), u(nx+1,:), v(:,1), v(:,ny+1)). The prescribed value is simply written into these elements. The nearest interior node is a full cell away from the boundary node, so its equation is built in the usual way. The boundary node is a neighbour with a known value, and the term a_nb·φ_b is moved to the right-hand side b.</li><li><strong>Tangential component.</strong> There are no nodes on the boundary: for example, the node u(i,1) closest to the bottom lies at height Δy/2. Face s of its CV coincides with the wall. There is no convection through the wall (F_s = 0, since v = 0), and the diffusive friction flux is computed over a distance of <strong>half a cell</strong>:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*odxsQg9GGwybur5QCRVf6Q.png" /></figure><p>The wall value acts as a neighbour with a known value: a_S = D_s stays in a_P, and a_S·u_wall goes into b.</p><pre>tangential (u at bottom):                 normal (v at bottom):<br><br> y = Δy/2  ── o  u_P  (interior)           y = Δy  ── o  v_P  (interior)<br>                 ↕ Δy/2                                 ↕ Δy<br> y = 0   ══════════════  wall, u_b         y = 0   ═══ o ═══  v_b  (on boundary)</pre><p><strong>Relation to ghost nodes.</strong> In Chorin’s method [8] the same condition is imposed through a ghost node beyond the wall with value u_gh = 2u_b − u_P. Substituting it into the usual difference gives (u_P − u_gh)/Δy = (u_P − u_b)/(Δy/2), the same formula. The two approaches are equivalent; Patankar simply builds the boundary condition into the coefficients instead of storing it in extra array elements.</p><h3>5.2. Types of velocity conditions</h3><p>Denote the normal component by u_n and the tangential one by u_t.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*j05OYxZXnhOkjSDKH3-6YA.png" /></figure><p>Here a_b is the coefficient coupling to the boundary value and D is the ordinary face conductance. At an inlet there is also a convective flux through the boundary, so the convective part of formula (2.3) is added to diffusion.</p><h3>5.3. Pressure correction</h3><p>Pressure has no physical boundary condition of its own. The condition for p’ follows from what the correction (4.6) does to the normal velocity at the boundary (Patankar, Ch. 6).</p><p><strong>Prescribed normal velocity</strong> (walls, inlet). The boundary velocity is already correct and is not corrected: u’_b = 0. Hence d_b = 0 for the boundary face, and the coefficient coupling to the outside in equation (4.7) is zero. The value of p’ beyond the boundary is not needed, and the known flow rate ρ·u_b·A_b enters b. This is the discrete analogue of the condition ∂p’/∂n = 0.</p><p><strong>Prescribed pressure</strong> (outlet to the atmosphere, flow driven by a pressure difference). The boundary pressure is already correct, so p’_b = 0: this is a Dirichlet condition, and the boundary value of p’ becomes a known neighbour. The normal velocity at such a boundary is not known in advance and is found from the correction (4.6) or from the mass balance.</p><h3>5.4. Pressure is relative</h3><p>In an incompressible fluid only the pressure gradient matters: adding any constant to p changes nothing in the momentum equations. If the normal velocity is prescribed on all boundaries (as in the cavity), then p’ is also determined only up to a constant. Formally this is seen from (4.7): in every cell a_P = Σ a_nb, the row sums of the matrix are zero, and the matrix is singular.</p><p>A solution of such a system exists only if the sum of the right-hand sides is zero. The sum of b over all cells is the total mass imbalance of the whole domain. Fluxes through interior faces cancel, leaving the fluxes through the boundary. In the cavity they are zero, so the condition is satisfied.</p><p>The level of p’ is fixed in one of two ways: set p’ = 0 in one cell, or let an iterative method work with the singular system and subtract the mean.</p><h3>6. Solving the linear systems</h3><p>At every SIMPLE iteration, three linear systems of the form (2.2) are solved: for u*, for v* and for p’. All have a five-point stencil: each row has at most five nonzero entries. But the properties of the systems differ.</p><ul><li><strong>Momentum equations.</strong> The matrix is non-symmetric: because of convection, a_E of node P is not equal to a_W of node E. On the other hand, it is diagonally dominant, a_P ≥ Σ a_nb, and with under-relaxation (Section 7) strictly so, which guarantees convergence of simple iterative methods. The coefficients change at every iteration.</li><li><strong>The p’ equation.</strong> The matrix is symmetric and, with velocity conditions on the whole boundary, singular (Section 5.4). This is an elliptic equation: a correction in one cell affects the whole domain, so simple iterative methods converge slowest on it. How well the corrected velocity conserves mass depends on how accurately it is solved.</li></ul><p><strong>An exact solution is not required.</strong> The coefficients are recomputed at the next iteration anyway, and p* is wrong until the very end. Solving intermediate systems to machine precision is pointless: reducing the residual by a few times is usually enough. What matters is the convergence of the outer iterations.</p><h3>6.1. The line-by-line method</h3><p>Patankar (Ch. 4) recommends the <strong>tridiagonal matrix algorithm</strong> (TDMA, also known as the Thomas algorithm). For a one-dimensional problem the equations have the form</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/999/1*UL6gseGY7D9IYZQdAEdc9A.png" /></figure><p>with c₁ = 0 and b_n = 0. The forward sweep computes the recurrence coefficients</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/904/1*euVQdtf4AlX6BHeF3uy58Q.png" /></figure><p>and the back substitution recovers the solution φ_n = Q_n, φ_k = P_k·φ_(k+1) + Q_k. The cost is O(n) operations.</p><p>In two dimensions the <strong>line-by-line TDMA</strong> is used. Take one grid line, for example column i. The values on the neighbouring lines i±1 are treated as known (the latest computed values are used), their contribution is moved to the right-hand side, and a tridiagonal system is solved along the line. All lines are swept this way, then the direction is switched: rows instead of columns. In one sweep, boundary information propagates along the entire line at once rather than one cell at a time as in Gauss–Seidel. That is why the method converges noticeably faster than point-by-point iterations. For the momentum equations one or two sweeps per SIMPLE iteration are usually enough; for p’, several.</p><h3>6.2. What the program uses</h3><p>In the test program the systems are assembled into sparse matrices and solved with a direct method, the \ operator (for sparse matrices Octave uses sparse LU factorization). The reasons:</p><ul><li><strong>Simplicity and speed in Octave.</strong> Loops in Octave are slow, while matrix assembly and the call to \ are fully vectorized.</li><li><strong>A small grid.</strong> For a 64×64 cavity each system has about 4000 unknowns, and the sparse factorization takes milliseconds.</li></ul><p>For large grids and 3D problems, direct methods require too much memory. Then line-by-line TDMA, SOR or multigrid methods are used. Iterative and direct methods are discussed in detail, using the heat equation as an example, in articles [9], [10].</p><h3>7. Under-relaxation and convergence</h3><p>The stability of the SIMPLE iterations is ensured by <strong>under-relaxation</strong>, an artificial slowing of the changes between iterations.</p><h3>7.1. Why it is needed</h3><p>Without relaxation SIMPLE usually diverges, for two reasons:</p><ul><li><strong>Nonlinearity.</strong> The coefficients of the momentum equations are computed from the velocity of the previous iteration. If the new velocity differs strongly from the old one, the coefficients become wrong, and the next iteration may “overshoot” the solution.</li><li><strong>The dropped term.</strong> Because of the simplification (4.5), the pressure correction p’ is overestimated: it has to compensate the mass imbalance on its own, whereas in reality the corrections of the neighbouring velocities would share that work.</li></ul><h3>7.2. Relaxing the momentum equations</h3><p>The simplest approach is to blend the new solution with the old one: u = α_u·uⁿᵉʷ + (1 − α_u)·uᵒˡᵈ. Patankar (Ch. 4) builds this blending directly into the discrete equation. From (4.1)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/754/1*xl4roKB5hahC64o7Ve3ZQw.png" /></figure><p>Substitute this value as u_eⁿᵉʷ into the blending u_e = u_eᵒˡᵈ + α_u·(u_eⁿᵉʷ − u_eᵒˡᵈ) and multiply by a_e/α_u:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Xgp95L7mpUDaeB8pbsyY_g.png" /></figure><p>Properties of this formulation:</p><ul><li>at convergence u_e = u_eᵒˡᵈ, and (7.1) reduces to the original equation (4.1). <strong>Relaxation does not change the converged solution</strong>, only the path to it;</li><li>the diagonal coefficient grows by a factor of 1/α_u, and diagonal dominance becomes strict. Iterative linear solvers converge faster;</li><li>the coefficient d_e in the correction formula (4.5) is computed from the increased coefficient: d_e = A_e / (a_e/α_u) = α_u·A_e / a_e.</li></ul><h3>7.3. Relaxing the pressure</h3><p>The pressure is corrected not by the full correction but by a fraction of it:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/659/1*5I5MaWwefNdo2SsQF4qnFw.png" /></figure><p>The velocity, however, is corrected by the <strong>full</strong> correction according to (4.6). Otherwise the corrected velocity would not satisfy continuity, which is the whole reason p’ was computed.</p><h3>7.4. Relaxation as a pseudo-time step</h3><p>Rewrite (7.1) by moving u_eᵒˡᵈ to the left-hand side:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7dugoo403oRq_ZHmA_oT3A.png" /></figure><p>The first term has the form of an implicit approximation of the transient term ρ·ΔV·(u − uᵒˡᵈ)/Δt with a “pseudo time step”</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/560/1*J03JmlfD-qg38u38wq1Ufw.png" /></figure><p>In other words, SIMPLE with under-relaxation is an implicit march in pseudo-time towards the steady solution, with a different step at each node. The smaller α_u, the smaller the step: the iterations are more stable, but more of them are needed.</p><h3>7.5. Choosing the relaxation factors</h3><p>There are no universal values; they are tuned to the problem. The typical range is α_u = 0.5…0.8, α_p = 0.2…0.8. Ferziger and Perić [7] show that for SIMPLE the rule</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/286/1*VC49IHIo8YSDYONM66acOQ.png" /></figure><p>is close to optimal, for example α_u = 0.7, α_p = 0.3; these are the values used in the program.</p><p>Signs of a poor choice: residuals grow or oscillate without decaying, so the factors should be reduced; residuals decrease very slowly and monotonically, so the factors can be increased.</p><h3>7.6. Convergence criterion</h3><p>The iterations are stopped when all discrete equations are satisfied with sufficient accuracy. For each equation a <strong>residual</strong> is computed: how far the current field is from satisfying the equation, summed over all nodes:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1-Cv5Lpa3k6zTa51U5kBXw.png" /></figure><p>and R_v is analogous to R_u. Here b_p’ is the right-hand side of equation (4.7), i.e. the mass imbalance, and ρU²L and ρUL are the force and flow-rate scales (per unit depth) that make the residuals dimensionless. The momentum residual is computed with the current fields before solving the system. Relaxation does not enter it: when u_e = u_eᵒˡᵈ, the relaxation terms in (7.1) cancel each other.</p><p>The computation stops when R_u, R_v and R_mass are below the prescribed tolerance. The criterion “the field has stopped changing” is worse: with strong relaxation the changes per iteration are small even when the solution is still far away.</p><h3>7.7. Unsteady problems</h3><p>SIMPLE also applies to unsteady problems. The transient term is discretized with the implicit Euler scheme: a_P⁰ = ρ·ΔV/Δt is added to a_P, and the term a_P⁰·φᵖʳᵉᵛ (the value from the previous time step) is added to b. At each time step the SIMPLE iterations are carried out to convergence. The scheme is implicit, so there is no Courant condition for stability, and the time step is limited only by accuracy. For unsteady problems the PISO and SIMPLEC variants (Section 8) are used more often, since they need fewer iterations per step.</p><h3>8. Variants of the method</h3><p>The simplification (4.5) makes SIMPLE simple but slow to converge. Several improvements are known.</p><ul><li><strong>SIMPLER</strong> (SIMPLE Revised; Patankar, Ch. 6). The pressure is obtained not from the correction but from a separate equation of the same form as (4.7). Instead of u* it contains “pseudo-velocities” û_e = (Σ a_nb·u_nb + b)/a_e, computed without the pressure. The correction p’ is used only to correct the velocity, not the pressure. If the velocity field is guessed correctly, SIMPLER immediately gives the correct pressure. An iteration is more expensive (one more equation), but significantly fewer iterations are needed.</li><li><strong>SIMPLEC</strong> (SIMPLE Consistent; Van Doormaal &amp; Raithby, 1984 [4]). Instead of dropping Σ a_nb·u’_nb, the neighbour corrections are assumed to be roughly equal to the correction at the node: Σ a_nb·u’_nb ≈ u’_e·Σ a_nb. This gives d_e = A_e / (a_e − Σ a_nb), where a_e is the diagonal coefficient including relaxation, i.e. a_e/α_u from (7.1): d_e = A_e / (a_e/α_u − Σ a_nb). Pressure relaxation then often becomes unnecessary (α_p = 1).</li><li><strong>PISO</strong> (Pressure-Implicit with Splitting of Operators; Issa, 1986 [5]). After the first correction, a second one is performed that accounts for the dropped term using the already computed u’. It was designed for unsteady problems: with a small time step it gives an accurate solution in one outer iteration per step.</li></ul><p>The test program, a lid-driven cavity flow computation in Octave, is available at: <a href="https://github.com/Semen1996/incompressible-flow-simple-method">https://github.com/Semen1996/incompressible-flow-simple-method</a>.</p><h3>References</h3><ol><li>Patankar S. V. <em>Numerical Heat Transfer and Fluid Flow.</em> — Hemisphere, 1980.</li><li>Patankar S. V., Spalding D. B. A calculation procedure for heat, mass and momentum transfer in three-dimensional parabolic flows. <em>Int. J. Heat Mass Transfer</em>, 15 (1972), 1787–1806.</li><li>Harlow F. H., Welch J. E. Numerical calculation of time-dependent viscous incompressible flow of fluid with free surface. <em>Physics of Fluids</em>, 8 (1965), 2182–2189.</li><li>Van Doormaal J. P., Raithby G. D. Enhancements of the SIMPLE method for predicting incompressible fluid flows. <em>Numerical Heat Transfer</em>, 7 (1984), 147–163.</li><li>Issa R. I. Solution of the implicitly discretised fluid flow equations by operator-splitting. <em>J. Comput. Phys.</em>, 62 (1986), 40–65.</li><li>Rhie C. M., Chow W. L. Numerical study of the turbulent flow past an airfoil with trailing edge separation. <em>AIAA Journal</em>, 21 (1983), 1525–1532.</li><li>Ferziger J. H., Perić M. <em>Computational Methods for Fluid Dynamics.</em> 3rd ed., Springer, 2002.</li><li>Simulating fluid flow with Chorin’s method. — <a href="https://github.com/Semen1996/incompressible-flow-chorin-method">https://github.com/Semen1996/incompressible-flow-chorin-method</a></li><li>Solving the steady-state heat equation. Part 1. The one-dimensional case. <a href="https://github.com/Semen1996/steady-state-heat-1d">https://github.com/Semen1996/steady-state-heat-1d</a></li><li>Solving the steady-state heat equation. Part 2. The two-dimensional case. <a href="https://github.com/Semen1996/steady-state-heat-2d">https://github.com/Semen1996/steady-state-heat-2d</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=398c40da9ac4" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Simulating a Fluid with Chorin’s Method]]></title>
            <link>https://medium.com/@semen.tolstoguzov96/simulating-a-fluid-with-chorins-method-11841672f881?source=rss-01347f1bf6b0------2</link>
            <guid isPermaLink="false">https://medium.com/p/11841672f881</guid>
            <category><![CDATA[physics]]></category>
            <category><![CDATA[fluid-dynamics]]></category>
            <category><![CDATA[cfd]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[numerical-methods]]></category>
            <dc:creator><![CDATA[Simon]]></dc:creator>
            <pubDate>Wed, 28 Oct 2026 16:42:42 GMT</pubDate>
            <atom:updated>2026-10-28T16:42:42.666Z</atom:updated>
            <content:encoded><![CDATA[<p>This article describes the numerical method implemented in this project: the equations, Chorin’s splitting scheme, the staggered grid, the discretisation of each term, the boundary conditions, the solution of the pressure Poisson equation, and the choice of the time step. The discretisation follows the book by Griebel, Dornseifer, Neunhoeffer, Numerical Simulation in Fluid Dynamics (hereafter “Griebel”); deviations from it are noted explicitly.</p><h3>1. Equations</h3><p>The flow of a viscous incompressible fluid is described by the Navier–Stokes equations:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/243/1*wPdrdzevoa9PVK94S76w-w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/707/1*yHLN7eMLXgqEcYvl_KU7-Q.png" /></figure><p>where <strong>u</strong> = (u, v) is the velocity, p the pressure, ρ the density, and ν the kinematic viscosity. There are no body forces. Bold <strong>u</strong> denotes the velocity vector, plain u its x-component.</p><p><strong>Differential operators.</strong> In two-dimensional Cartesian coordinates the “nabla” operator is the vector of partial derivatives</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/397/1*d5hPGeDgwF6qnOIZdugCtw.png" /></figure><p>and all operators in the equations are built from it.</p><ul><li><strong>Divergence</strong> ∇·<strong>u</strong> — the dot product of ∇ with a vector; the result is a scalar:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/415/1*yhRD32M8j9KVChjvXyCL-A.png" /></figure><p>It is the relative rate of change of the volume of a fluid parcel (the balance of inflow and outflow through a small volume). The condition ∇·<strong>u</strong> = 0 expresses incompressibility: as much fluid flows into any volume as flows out of it.</p><ul><li><strong>Gradient</strong> ∇p — nabla applied to a scalar; the result is a vector:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/420/1*40zJAWwdKTPZl4Z6d2ToRA.png" /></figure><p>It points in the direction of the fastest pressure increase, so the force −∇p (per unit volume) pushes the fluid from high-pressure regions towards low-pressure ones.</p><ul><li><strong>Convective derivative</strong> (<strong>u</strong>·∇)<strong>u</strong>. First, <strong>u</strong> and ∇ are combined into a scalar operator — the derivative along the flow:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/462/1*S2Bo2Y1kzADtMWALwkTGbA.png" /></figure><p>which is then applied to each velocity component; the result is a vector:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*1C_gj9BohcfNXlzDdvGZdQ.png" /></figure><p>Together with ∂<strong>u</strong>/∂t it gives the acceleration of a fluid parcel, D<strong>u</strong>/Dt = ∂<strong>u</strong>/∂t + (<strong>u</strong>·∇)<strong>u</strong>: the parcel’s velocity changes not only with time at a fixed point, but also because the parcel is carried to a point where the velocity is different. This is the only nonlinear term in the equations.</p><ul><li><strong>Laplacian</strong> Δ = ∇·∇ — the divergence of the gradient, a second-order scalar operator:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/393/1*SiDHoM7_Dlb7r5NzgZ_tVQ.png" /></figure><p>It is applied to a vector component-wise:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/509/1*tjk53eXh0Fl9I9oeIKV1Tw.png" /></figure><p>The Laplacian is proportional to the deviation of the value at a point from the average over its neighbourhood, so the term νΔ<strong>u</strong> describes viscous diffusion: friction evens out the velocity of neighbouring fluid layers.</p><p><strong>Component form.</strong> Substituting these expressions gives a system of three scalar equations for the three unknowns u, v, p:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/338/1*inV7xxizceP7iN5yeb4nFg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*52854MWnFyfZWdXCKSH1Ww.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1022/1*vDExf6nYFzckpL3hdFkSPg.png" /></figure><p>The convective term (<strong>u</strong>·∇)<strong>u</strong> can be written in two forms. For the u component, expand the derivatives of the products:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OlU0hxGoEZrfDnuiB8XNpg.png" /></figure><p>Since ∇·<strong>u</strong> = 0, the second term vanishes, and the advective form (the first brace) coincides with the <strong>conservative</strong> (divergence) form, which is the one used in the code:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nK6ZGFf_uXwYeYz95aJrCw.png" /></figure><p>or, in vector notation, (<strong>u</strong>·∇)<strong>u</strong> = ∇·(<strong>u</strong> ⊗ <strong>u</strong>).</p><p>A distinctive feature of the incompressible formulation: pressure has no evolution equation of its own. It acts as a Lagrange multiplier that at every instant “adjusts itself” so that the velocity field stays divergence-free. Chorin’s method exploits exactly this property.</p><h3>2. Chorin’s Scheme (Projection Method)</h3><h3>2.1. Idea</h3><p>The method was proposed by A. Chorin (1968) and independently by R. Temam (1969). The time step tⁿ → tⁿ⁺¹ = tⁿ + Δt is split into two parts:</p><ol><li><strong>Predictor: move the fluid without pressure.</strong> This gives an intermediate field <strong>u</strong>* which in general violates incompressibility: ∇·<strong>u</strong>* ≠ 0.</li><li><strong>Corrector: pressure fixes the velocity.</strong> Choose the pressure p so that its gradient corrects <strong>u</strong>* exactly as much as needed to satisfy the incompressibility equation:</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/452/1*_ihM1hxF0MUYn0sNSsPqDw.png" /></figure><p>Where fluid has “accumulated”, the pressure comes out high. Its gradient pushes the excess to the neighbours, and in the end ∇·<strong>u</strong>ⁿ⁺¹ = 0.</p><p><strong>Why such a correction always exists and is unique.</strong> This follows from the Helmholtz–Hodge decomposition (statement and proof — [7, § 1.3]; survey — [8]). Any vector field can be split, and in a unique way, into two parts:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/864/1*UwdDxbyXfxdUtCIxKR9ffQ.png" /></figure><p>The first part describes how the fluid swirls and flows without being compressed. The second describes only the “excess” compression and expansion. The corrector simply discards the second part.</p><h3>2.2. Three Stages</h3><p><strong>Stage 1. Predictor</strong> — an explicit Euler step for convection and diffusion, without pressure:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/697/1*biBGVIGQw92BiYWCg_RMTA.png" /></figure><p><strong>Stage 2. Pressure Poisson equation.</strong> We seek the pressure pⁿ⁺¹ whose gradient will make the velocity divergence-free in stage 3. Stage 3 has not been performed yet, but we already know its formula. So we write two requirements on <strong>u</strong>ⁿ⁺¹:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gDDSFLnkE0S0z4gQw0q1Wg.png" /></figure><p><strong>Derivation.</strong> Take the divergence of the first equality and substitute the second:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/735/1*Tima8pxL6o2Ll-ZdR0k9Xw.png" /></figure><p>Since ∇·∇p = Δp (the divergence of the gradient is the Laplacian), we obtain</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/855/1*lL770ucFWnrjQuePtALh0w.png" /></figure><p>The velocity <strong>u</strong>ⁿ⁺¹ has dropped out of the equation. What remains is a single scalar equation for a single unknown function p, with a known right-hand side: <strong>u</strong>* was already computed in stage 1.</p><p><strong>Stage 3. Corrector</strong>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/516/1*Hqu3BHqsp1OQFDRbIJ-Ksw.png" /></figure><p>after which the boundary values are set again.</p><h3>3. Staggered (MAC) Grid</h3><p>The domain is divided into n_x × n_y cells with spacings Δx = L/n_x, Δy = H/n_y. The unknowns are stored at different points of a cell:</p><ul><li>p — at the cell centre;</li><li>u — at the centres of the vertical (left/right) faces;</li><li>v — at the centres of the horizontal (bottom/top) faces.</li></ul><pre>v(j+1,i)<br>     +-------o-------+<br>     |               |<br>u(j,i) o     * p     o u(j,i+1)<br>     |               |<br>     +-------o-------+<br>          v(j,i)</pre><p>This arrangement (“marker-and-cell”, Harlow &amp; Welch, 1965) has three important properties:</p><ol><li>The pressure difference between neighbouring cells falls exactly on the face where the corresponding velocity component lives — the pressure gradient is computed without interpolation.</li><li>The velocity divergence in a cell is the difference of fluxes through its faces, again without interpolation.</li><li>There are no “checkerboard” pressure oscillations, which are typical of collocated grids.</li></ol><h3>4. Spatial Discretisation</h3><p>Below we use “physical” half-integer indices: u_(i+1/2, j) is the velocity on the right face of cell (i, j), v_(i, j+1/2) on the top face, p_(i,j) at the centre.</p><h3>4.1. Diffusion</h3><p>Five-point Laplacian, second-order accurate:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5U-_h7taa6bq5MMMyjsTfw.png" /></figure><p>and similarly for v.</p><h3>4.2. Convection: a Blend of Central and Donor-Cell Schemes</h3><p>Each convective derivative is written as a difference of fluxes through the faces of a control volume around the velocity node, for example</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Q_Suy7wUPrxku-Bxm16xkw.png" /></figure><p>The flux through a face depends on the <strong>transporting velocity</strong> a on that face and on the values of the <strong>transported quantity</strong> φ_L, φ_R on either side of it:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/732/1*X9ZNWLJ3wSjg6y8TQBCBXQ.png" /></figure><ul><li>γ = 0 — central scheme (second order, but unstable/oscillatory at large grid Reynolds numbers);</li><li>γ = 1 — donor-cell scheme (upwind, first order): for a &gt; 0 the flux is aφ_L, for a &lt; 0 it is aφ_R, i.e. the quantity is taken “from the donor cell” upstream;</li><li>intermediate γ give a linear blend. The upwind contribution is equivalent to an artificial viscosity ~γ|a|Δx/2.</li></ul><p>The transporting velocities are the arithmetic mean of the two nearest nodes. For the u equation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FuX6plWdua_BkgaQqiR9vg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-MJXqJSncnXFI7obUmYkLg.png" /></figure><p>and symmetrically for the v equation. This is exactly Griebel’s scheme (formulas 3.19–3.20 of the book), merely written in terms of a flux function.</p><p>The conservative form guarantees that the flux leaving one control volume enters the neighbouring one — momentum is neither created nor lost by the scheme inside the domain.</p><p><strong>Why the upwind contribution is needed.</strong> A pure central scheme produces unphysical sawtooth oscillations at high Reynolds numbers.</p><h3>4.3. Divergence and Gradient</h3><p>Divergence of <strong>u</strong>* at the cell centre:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OSldfzL31B9vkl8eqgIJJA.png" /></figure><p>Pressure gradient on the faces:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fORU2rhX3f1YlZ0A8wT8Zg.png" /></figure><h3>5. Boundary Conditions</h3><p>This section describes boundary conditions on a MAC grid in general form: walls, inflow, outflow, symmetry, periodicity.</p><h3>5.1. How the Boundary Works on a MAC Grid</h3><p>The domain boundary runs along cell faces. On each side one velocity component is <strong>normal</strong> to the boundary and the other is <strong>tangential</strong>, and their nodes are placed differently:</p><ul><li><strong>normal component</strong> — the nodes lie <strong>exactly on the boundary</strong>, and the value is set directly;</li><li><strong>tangential component</strong> — there are no nodes on the boundary. The nearest interior node is half a step away from the boundary, and beyond the boundary lies a <strong>ghost</strong> node. The condition is imposed through the ghost value.</li></ul><pre>tangential (u at the bottom):          normal (v at the bottom):</pre><pre> y = +Δy/2  ── o  u_in  (interior)      y = +Δy  ── o  v_in  (interior)<br> y = 0   ══════════════  boundary       y = 0   ═══ o ═══  v_b  (on boundary)<br> y = −Δy/2  ── o  u_gh  (ghost)</pre><p>Any velocity condition reduces to two elementary techniques.</p><p><strong>Prescribed value (Dirichlet), φ = φ_b on the boundary.</strong> For the normal component simply φ_(on boundary) = φ_b. For the tangential component the boundary value is obtained by linear interpolation between the ghost and interior nodes, so we require their mean to equal φ_b:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/873/1*cJmsY55fB5zujeY9EipqFg.png" /></figure><p>Simply writing φ_gh = φ_b is wrong: the boundary value would then be (φ_b + φ_in)/2 ≠ φ_b.</p><p><strong>Prescribed normal derivative (Neumann), ∂φ/∂n = 0.</strong> The value on the far side of the boundary is copied from the near side: φ_gh = φ_in for the tangential component and φ_(on boundary) = φ_in for the normal one. A nonzero derivative g gives a shift: φ_gh = φ_in + g·h, where h is the spacing across the boundary.</p><h3>5.2. Types of Velocity Conditions</h3><p>Denote the normal component by u_n and the tangential one by u_t. The standard set:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MszhoQlSXhQbKxhiOlbujw.png" /></figure><p>Notes:</p><ul><li><strong>No-slip and moving wall.</strong> A viscous fluid neither slides along a wall nor passes through it. For a stationary wall the ghost value is the mirror image with a minus sign: the straight line through u_gh and u_in crosses zero exactly at the wall.</li><li><strong>Free-slip.</strong> No friction against the wall, only impermeability. The same formulas describe an axis or plane of symmetry: there is neither flux nor shear across it.</li><li><strong>Inflow.</strong> The profile U_in is specified by the user: constant, parabolic, etc.</li><li><strong>Outflow.</strong> The flow “leaves as it is”: normal derivatives are set to zero. This is an approximate condition. The outflow boundary is placed far from the region of interest so that it does not distort the solution.</li><li><strong>Periodicity.</strong> The domain is “glued”: the right boundary is the same face as the left one. The normal-component nodes on the boundary become ordinary unknowns (shared by both sides), and the ghost columns of the tangential component are filled with values from the other side: for periodicity in x, v(:,1) = v(:,end-1), v(:,end) = v(:,2).</li></ul><p>The same rules apply on the faces of internal obstacles: obstacle cells are excluded from the computation, and their faces are walls.</p><h3>5.3. Pressure</h3><p>Pressure has no physical boundary condition of its own. It follows from what the corrector <strong>u</strong>ⁿ⁺¹ = <strong>u</strong>* − (Δt/ρ)∇p does to the normal velocity on the boundary. There are two options.</p><p><strong>Neumann, ∂p/∂n = 0.</strong> Used where the normal velocity on the boundary is <strong>prescribed</strong>: walls, inflow, free-slip, and also outflow with a copied u_n. The normal velocity already has the required value and must not change during the correction. From u_nⁿ⁺¹ = u_n* − (Δt/ρ)·∂p/∂n and u_nⁿ⁺¹ = u_n* = u_(n,b) it follows that</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/368/1*YmF2p1pyq9KtiOKrv3oyCQ.png" /></figure><p>Discretely: the divergence of a boundary cell includes the prescribed flux through the boundary, and the pressure gradient on the boundary face is not computed. This is equivalent to a ghost pressure p₀ = p₁, for which the term (p₀ − p₁)/h² in the Laplacian vanishes. Hence the diagonal of the one-dimensional matrix has −1 instead of −2 at such an end.</p><p>This condition is not physical: the true normal pressure gradient at a wall equals ρν·∂²u_n/∂n² and is nonzero. This produces a numerical boundary layer in the pressure error of thickness O(√(νΔt)).</p><p><strong>Dirichlet, p = p_b.</strong> Used where the <strong>pressure</strong> is prescribed and the normal velocity is not known in advance: outflow to the atmosphere, flow driven by a pressure difference. On such a boundary the normal velocity is not imposed but found by the corrector. Via the ghost cell p₀ = 2p_b − p₁:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/723/1*lnEh2JV073FqK7rBKCgMfw.png" /></figure><p>i.e. −3 on the diagonal, and the known term 2p_b/h² is moved to the right-hand side. The gradient on the boundary face, (p₁ − p_b)/(h/2), enters the corrector.</p><p><strong>Periodicity.</strong> The matrix “wraps around”: the first and last cells in the periodic direction become neighbours. The one-dimensional matrix is circulant, with −2 along the whole diagonal and ones in the corners.</p><p>If at least one part of the boundary carries a Dirichlet condition, the pressure level is determined and the matrix is nonsingular. If the conditions are Neumann or periodic everywhere, the pressure is determined only up to a constant, and its level must be fixed.</p><h3>6. Solving the Linear System for Pressure</h3><p>The Poisson equation from stage 2, written in every grid cell, is a system of linear equations A<strong>p</strong> = <strong>b</strong> with N = n_x·n_y unknowns. The system has the following properties:</p><ul><li><strong>Sparsity.</strong> Each row has at most five nonzero entries: a cell is coupled only to its four neighbours (five-point Laplacian, section 4.1).</li><li><strong>Constant matrix, changing right-hand side.</strong> A depends only on the grid, while <strong>b</strong> = (ρ/Δt)∇·<strong>u</strong>* changes every step. So the system has to be solved anew at every time step, and this is usually the most expensive part of the computation.</li><li><strong>Singularity.</strong> With Neumann conditions on all walls (section 5.3) the pressure is determined only up to a constant, and the matrix is singular. The pressure level has to be fixed, but only its gradient is physically meaningful.</li></ul><p>Such systems are solved by iterative or direct methods. Both approaches are discussed in detail, using the heat equation as an example, in articles [9], [10]. The project uses successive over-relaxation for the following reasons:</p><ul><li><strong>Memory.</strong> Iterative methods store only the pressure array itself (plus an array of old values for the Jacobi method) — O(N). The matrix need not be assembled: the formula “cell value in terms of its neighbours” is enough. A direct method stores the factors L, U, and elimination fills in the zeros inside the matrix band: in 2D this means O(N log N) nonzeros, in 3D O(N^(4/3)), and the factorisation costs O(N²) operations.</li><li><strong>Simplicity.</strong> The method hardly changes when going from 2D to 3D or to domains with obstacles: only the cell’s neighbours and the boundary formulas change.</li><li><strong>Accuracy.</strong> There is no point in solving the system more accurately than the scheme error ~h², and iterations can be stopped at the required tolerance. A good initial guess from the previous step makes this cheap.</li></ul><p>The price is slow convergence: the number of iterations grows as O(N_x) even with the optimal ω, and the convergence rate is very sensitive to the choice of ω. In addition, after the corrector the velocity is divergence-free only up to the tolerance ε, not up to round-off. For more on SOR, the choice of ω, and the stopping criterion, see the articles “Solving the Steady-State Heat Equation” [9, § 3.3], [10, § 3.3].</p><h3>6.1. Successive Over-Relaxation (SOR)</h3><p>The discrete Poisson equation in cell (i, j) is the five-point Laplacian from section 4.1 with right-hand side b_(i,j) = (ρ/Δt)(∇·<strong>u</strong>*)_(i,j). Solve it for the central value:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*j8Cxo6A6BKknE-2lHoEHlQ.png" /></figure><p>The cells are visited one after another, and each immediately uses the already updated values of its neighbours (the Gauss–Seidel method). The correction is then “amplified” with the relaxation parameter ω:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/902/1*uJ6V7Aif_jL8zTt1a2KP2A.png" /></figure><p>All values are overwritten “in place” in a single array.</p><p>Specifics for pressure:</p><ul><li><strong>Boundary condition</strong> ∂p/∂n = 0 is imposed through a ghost layer: before each iteration the values in the wall-adjacent cells are copied into the ghost cells (section 5.3).</li><li><strong>Initial guess</strong> — the pressure from the previous time step. The pressure field changes little from step to step, so few iterations are needed.</li><li><strong>Stopping criterion</strong> — the relative residual ‖b − A<strong>p</strong>‖ / ‖b‖ &lt; ε.</li><li><strong>Pressure level.</strong> With Neumann conditions on all walls the pressure is determined only up to a constant. SOR converges on such a system too, provided the right-hand side sums to zero. Therefore its mean is subtracted from b (a correction at round-off level), and the mean of the computed p is subtracted from p. This does not affect the velocity: a constant shift does not change the gradient.</li></ul><h3>6.2. Alternative: Direct Methods</h3><p>Direct methods for this system are described in the same articles [9, § 3.2], [10, § 3.2]: <strong>sparse LU factorisation</strong>, <strong>Cholesky factorisation</strong>, <strong>block tridiagonal (Thomas) algorithm</strong>, <strong>fast direct solvers</strong>.</p><p>For a two-dimensional cavity of moderate size, sparse LU with a single factorisation is faster than SOR. Iterative methods become preferable as the grid grows and in 3D, where fill-in of the factors eats up memory.</p><h3>7. Time Step</h3><p>The predictor is explicit, so the step is limited by two stability conditions.</p><p><strong>Diffusion</strong> (explicit scheme for the heat equation on a five-point stencil):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/611/1*W8_7y0xIoVOD-Olr5Y0xdQ.png" /></figure><p><strong>Convection</strong> (the Courant–Friedrichs–Lewy condition in two-dimensional form):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/592/1*qaU8CUrOXmBcDRnRKsbY4Q.png" /></figure><p>The time step is therefore:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nLYHf_da0rBTEy4fC_7TyA.png" /></figure><p>where cfl &lt; 1.</p><p>When estimating |u|_max, |v|_max, <strong>ghost values are excluded</strong>: in the ghost row above the lid, u = 2U_lid − u_inner can reach almost 2U_lid, which would halve the step for no physical reason.</p><p><strong>Donor-cell weight.</strong> At the same time we compute</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/899/1*BrvGG8PMn6u1lRNd3ekBrw.png" /></figure><p>which corresponds to Griebel’s stability condition for the hybrid scheme, γ ≥ max(|u|Δt/Δx, |v|Δt/Δy). The smallest admissible value is taken, so the scheme stays as close as possible to the central one (less dissipative). The upper bound of one is a safeguard: when the CFL condition holds, it never activates.</p><p>The MATLAB implementation of the lid-driven cavity flow problem can be found here: <a href="https://github.com/Semen1996/incompressible-flow-chorin-method">https://github.com/Semen1996/incompressible-flow-chorin-method</a></p><h3>References</h3><ol><li>Griebel M., Dornseifer T., Neunhoeffer T. <em>Numerical Simulation in Fluid Dynamics: A Practical Introduction.</em> SIAM, 1998.</li><li>Chorin A. J. Numerical solution of the Navier–Stokes equations. <em>Mathematics of Computation</em>, 22 (1968), 745–762.</li><li>Temam R. Sur l’approximation de la solution des équations de Navier–Stokes par la méthode des pas fractionnaires. <em>Arch. Rational Mech. Anal.</em>, 33 (1969), 377–385.</li><li>Harlow F. H., Welch J. E. Numerical calculation of time-dependent viscous incompressible flow of fluid with free surface. <em>Physics of Fluids</em>, 8 (1965), 2182–2189.</li><li>Ghia U., Ghia K. N., Shin C. T. High-Re solutions for incompressible flow using the Navier–Stokes equations and a multigrid method. <em>J. Comput. Phys.</em>, 48 (1982), 387–411.</li><li>Guermond J.-L., Minev P., Shen J. An overview of projection methods for incompressible flows. <em>Comput. Methods Appl. Mech. Engrg.</em>, 195 (2006), 6011–6045.</li><li>Chorin A. J., Marsden J. E. <em>A Mathematical Introduction to Fluid Mechanics.</em> 3rd ed., Springer, 1993. — § 1.3: the Helmholtz–Hodge decomposition and its connection to pressure and the projection method.</li><li>Bhatia H., Norgard G., Pascucci V., Bremer P.-T. The Helmholtz–Hodge decomposition — a survey. <em>IEEE Trans. Visualization and Computer Graphics</em>, 19(8) (2013), 1386–1404.</li><li>Solving the Steady-State Heat Equation. Part 1. The One-Dimensional Case. <a href="https://github.com/Semen1996/steady-state-heat-1d">https://github.com/Semen1996/steady-state-heat-1d</a></li><li>Solving the Steady-State Heat Equation. Part 2. The Two-Dimensional Case. <a href="https://github.com/Semen1996/steady-state-heat-2d">https://github.com/Semen1996/steady-state-heat-2d</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=11841672f881" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solving the Steady-State Heat Equation. Part 2. The Two-Dimensional Case]]></title>
            <link>https://medium.com/@semen.tolstoguzov96/solving-the-steady-state-heat-equation-part-2-the-two-dimensional-case-2278cb439dd2?source=rss-01347f1bf6b0------2</link>
            <guid isPermaLink="false">https://medium.com/p/2278cb439dd2</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[thermodynamics]]></category>
            <category><![CDATA[numerical-methods]]></category>
            <category><![CDATA[physics]]></category>
            <dc:creator><![CDATA[Simon]]></dc:creator>
            <pubDate>Tue, 20 Oct 2026 21:20:04 GMT</pubDate>
            <atom:updated>2026-10-20T21:20:04.934Z</atom:updated>
            <content:encoded><![CDATA[<p>In the first part we solved the problem for a rod. There the temperature depended on a single coordinate, the answer was known in advance (a linear profile), and the system of equations was tridiagonal and was solved by the Thomas algorithm in O(N) operations. Now we move from a rod to a plate. The equation barely changes: a second derivative with respect to y is added. But each grid node now has four neighbours instead of two, and that changes everything else. The matrix is no longer tridiagonal, the number of unknowns grows by a factor of hundreds, and the Thomas algorithm can no longer be applied directly.</p><p>In this article we follow the same path as in the first part: the equation and boundary conditions, the finite-difference scheme, the linear system and its properties. Then we look at what happens to direct methods in two dimensions and why iterative methods (Jacobi, Gauss–Seidel, successive over-relaxation) come to the fore here.</p><h3>1. Problem Statement</h3><p>Consider a rectangular plate of size L × H. We assume the plate is thin and its flat faces are thermally insulated, so heat flows only in the xy plane and the temperature depends on two coordinates: T = T(x, y).</p><p>We are interested in the steady-state heat equation without sources and with constant λ. In two dimensions the Laplace operator Δ contains two second derivatives:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Is5KxM5YZgRjY5_pYEG7Lg.png" /></figure><p><strong>Boundary conditions</strong> are the same as in the first part: first kind (prescribed temperature, Dirichlet), second kind (prescribed heat flux, Neumann) and third kind (heat exchange with the surroundings, Robin). The difference is that the boundary now consists of four sides rather than two points.</p><p>As in the one-dimensional case, if second-kind conditions are imposed on the entire boundary, the solution is determined only up to a constant, and the fluxes must be consistent: as much heat as enters the plate through some sides must leave through the others. Therefore a first- or third-kind condition must be imposed on at least part of the boundary.</p><h3>2. Finite Difference Method</h3><h3>2.1 Grid and Difference Scheme</h3><p>Divide the plate into N_x − 1 equal intervals in x and N_y − 1 equal intervals in y. This gives a rectangular grid of N_x × N_y nodes with steps</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WFA8FvaXyVYGAybhS12xQA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/622/1*IdL5WTObnRwIVZ2TFXMh1Q.png" /></figure><p>The node with index i in x and j in y has coordinates xᵢ = (i − 1)Δx, yⱼ = (j − 1)Δy; we denote its temperature by Tᵢ,ⱼ.</p><p>Replace each second derivative with a difference:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2tg9ZBwc_q7CzS48HAYsRQ.png" /></figure><p>ach equation involves five nodes: the node itself and its four neighbours — left, right, below and above. This scheme is called the <strong>five-point stencil</strong> (the “cross”).</p><p>Most often equal steps Δx = Δy = h are used. Then, multiplying (2) by h², we get</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FY5wKg440htiGCUH-q7Jwg.png" /></figure><p>or</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FUXrL4Gvfv_y5sa7pSVtKQ.png" /></figure><p>With different steps the average becomes weighted:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4VC9rloiYftawmHsv3KMVQ.png" /></figure><p>Neighbours along the direction with the smaller step get the larger weight. From here on, to keep the formulas simple, we assume Δx = Δy = h.</p><h3>2.2 Boundary Conditions</h3><p>Equations (2) are written only for interior nodes. Nodes on the sides of the plate, as in the first part, are determined by the boundary conditions. The formulas are the same as in the one-dimensional case, only now they are written for every node along a side. The neighbour through which a boundary node is expressed is taken along the normal to the side, into the plate.</p><p><strong>First-kind boundary conditions:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RF3BHaVlOjf3T8FC5whXeQ.png" /></figure><p>The values may depend on the position of the node along the side: T_L = T_L(yⱼ), etc.</p><p><strong>Second-kind boundary conditions:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*K_ep6Kbb1lBVpGPl_YRPJA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*k6UFD9cW2tDg_TBZVsYKFA.png" /></figure><p>Here q &gt; 0 means heat flowing out of the plate. A common case is an insulated side, q = 0: then the boundary node is simply equal to its neighbour.</p><p><strong>Third-kind boundary conditions:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4v0Ecgzd0WTuZ2U2vRLO3g.png" /></figure><p>and similarly for the other sides. On the bottom and top sides the Biot number uses the step Δy: Bi_B = α_B Δy / λ.</p><p><strong>Corner nodes.</strong> Look at stencil (3): the neighbours of interior node (2, 2) are (1, 2) and (2, 1), but not the corner (1, 1). The boundary conditions also link a boundary node only to its neighbour along the normal. As a result, <strong>corner nodes do not enter any equation</strong> and do not affect the solution. This is convenient, because two sides with different conditions meet at a corner and it would be unclear which one to satisfy. For a nicer plot, the corner is usually assigned the average of the two adjacent boundary nodes.</p><h3>2.3 Node Numbering and Matrix Structure</h3><p>To write the system as AT = b, the unknowns must be arranged in a single column. The temperature is now a two-dimensional table Tᵢ,ⱼ, and it has to be “unrolled” into a vector. Nodes are usually numbered by grid rows: first all nodes of the bottom row from left to right, then the next row, and so on. Node (i, j) gets the number</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tfLZ7RJ5ng2ESl7v-hnnrg.png" /></figure><p>With this numbering, the x-neighbours of node k have numbers k − 1 and k + 1, and the y-neighbours have numbers k − N_x and k + N_x: to get to the adjacent row you have to skip over a whole row. Therefore the matrix row corresponding to an interior node contains five nonzero entries:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*pQWLFeLhd3yJYXMdrMCWuA.png" /></figure><p>The nonzero entries of the matrix lie on <strong>five diagonals</strong>: the main one, the two adjacent to it (x-couplings), and two at distance N_x from the main one (y-couplings). Between them are bands of zeros.</p><p>If, as in the first part, the boundary nodes are kept among the unknowns, the rows for boundary nodes with first-kind conditions contain a single one on the diagonal. For analysis and hand calculation it is more convenient to eliminate them: move the known boundary temperatures to the right-hand side and keep only the interior nodes as unknowns. There are n × m of them, where n = N_x − 2, m = N_y − 2. Let us also multiply the equations by −1 so that the diagonal becomes positive. Then the matrix has a <strong>block tridiagonal</strong> form:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*uZssPURw8EyuLlIDlaD4aQ.png" /></figure><p>where B is a tridiagonal n × n matrix (couplings within one grid row), I is the identity matrix of the same size (couplings with adjacent rows), and there are m blocks on the diagonal in total. The right-hand side b is nonzero only for nodes that have a neighbour on the boundary: that is where the known boundary temperatures go.</p><p>Compare with the first part: there the whole matrix was a single block of the form B (with 2 instead of 4). Now there are many such blocks, and they are coupled to each other.</p><p><strong>Kronecker notation.</strong> The fact that the two-dimensional matrix is assembled from one-dimensional ones can be written as a single formula. The <strong>Kronecker product</strong> P ⊗ Q is the block matrix in which each entry pₖₗ of P is replaced by the block pₖₗ Q:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Q4HapLgvWTY6JV4XNxvNVA.png" /></figure><p>Denote by Kₙ = tridiag(−1, 2, −1) the n × n matrix — this is the rod matrix from the first part after eliminating the boundary nodes and multiplying by −1. Then</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*oqqVsyEf5A-W6djQgqbybQ.png" /></figure><ul><li>The first term Iₘ ⊗ Kₙ is m copies of Kₙ on the diagonal: couplings along x within each grid row.</li><li>The second term Kₘ ⊗ Iₙ consists of blocks 2I on the diagonal and −I next to it: couplings between adjacent rows, i.e. along y.</li><li>On the diagonal they add up: Kₙ + 2I = tridiag(−1, 4, −1) = B.</li></ul><p>The order of the factors depends on the numbering. With the numbering k = i + (j − 1) N_x, the index i changes fastest, so the x matrix is on the right.</p><p>For example, with n = m = 2 and K₂ = [2 −1; −1 2]:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*iVNsAAbxGHfJGOpyIY1N1w.png" /></figure><p>This is exactly the matrix we will get in the example of Section 2.4.</p><p>Notation (4) is useful for several reasons.</p><ol><li><strong>Eigenvalues.</strong> If Kₙv = μv and Kₘw = νw, then A (w ⊗ v) = (μ + ν)(w ⊗ v). The eigenvectors of the two-dimensional matrix are products of one-dimensional ones, and the eigenvalues are sums of one-dimensional ones. Fast direct methods are based on this.</li><li><strong>The three-dimensional case.</strong> There are three terms:</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*r8to40eKqWJO_IFwv1F4VQ.png" /></figure><h3>2.4 Example: a 4 × 4 Plate</h3><p>Take a square plate with N_x = N_y = 4 nodes. Let the top side be held at T_T = 100 and the other three at 0 (first-kind boundary conditions). There are only four interior nodes: T₂,₂, T₃,₂ (bottom row), T₂,₃, T₃,₃ (top row).</p><p>Write equation (3) for each of them, multiplied by 4. The boundary neighbours are known: zeros below, left and right, 100 above.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NJ5iC7uClNA2tp-TqLdnrA.png" /></figure><p>In matrix form (unknowns ordered row by row: T₂₂, T₃₂, T₂₃, T₃₃):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HalfcdGAwAvGpwLQEfY_CQ.png" /></figure><p>The block structure from Section 2.3 is visible: blocks B = [4 −1; −1 4] on the diagonal and −I off it. Note the zeros at positions (2, 3) and (3, 2): nodes T₃,₂ and T₂,₃ are adjacent in the vector, but they are not neighbours on the grid (they are located diagonally from each other).</p><p>The problem is symmetric about the vertical axis of the plate, so T₂,₂ = T₃,₂ = a and T₂,₃ = T₃,₃ = c. From the first and third equations:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*d_bxDhudn9XTkv1SlEpd4Q.png" /></figure><p>Hence</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KajUwwF-cJbyS9YzXb8yHw.png" /></figure><h3>3. Solving the Linear System</h3><h3>3.1 Matrix Properties</h3><p>Let us compare the matrix of the two-dimensional problem with the one-dimensional one.</p><ol><li><strong>Size.</strong> There are now N = N_x N_y unknowns. For N_x = N_y = 100 that is already 1⁰⁴ unknowns, for N_x = N_y = 1000 it is 1⁰⁶.</li><li><strong>Sparsity.</strong> Each row has at most five nonzero entries, at most 5N out of N² in total. For N = 1⁰⁴ that is 5 · 1⁰⁴ out of 1⁰⁸, i.e. 0.05 %. The matrix is even sparser than in the one-dimensional problem.</li><li><strong>Band structure.</strong> All nonzero entries lie within a band of width N_x on either side of the main diagonal. Almost everything inside this band is zero, but, as we will see, these zeros fill in during Gaussian elimination.</li><li><strong>Diagonal dominance.</strong> In interior rows |4| = 1 + 1 + 1 + 1 — an equality; in rows next to a first-kind boundary — a strict inequality (some neighbours have moved to the right-hand side). As in the first part, this is sufficient for the Jacobi and Gauss–Seidel methods to converge.</li></ol><p>The main difference from the first part: the matrix is <strong>not tridiagonal</strong>. The Thomas algorithm in its original form is not applicable, and Gaussian elimination runs into the size of the system.</p><h3>3.2 Direct Methods. The Block Thomas Algorithm</h3><p>Collect the temperatures of the j-th grid row into a vector 𝐓ⱼ. Then the system from Section 2.3 takes the form</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rU3eE1guGtJeeAjuayTIiQ.png" /></figure><p>.e. it is the same tridiagonal system (3) from the first part, except that its elements are matrices and vectors. So formally the Thomas algorithm applies: we seek 𝐓ⱼ = Pⱼ𝐓ⱼ₊₁ + 𝐑ⱼ and, repeating the derivation from Part 1 (Section 3.2.2), obtain</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*LGmuYhpuWiQTKKGhKJgqUQ.png" /></figure><p>But now Pⱼ are dense N_x × N_x matrices, and they have to be inverted at every step, which costs ∼N_x³ operations. Over all N_y rows this gives ∼N_x³ N_y = N_x⁴.</p><p><strong>Fast direct methods.</strong> For a rectangle with constant coefficients there are special methods that use a discrete analogue of separation of variables: the solution is expanded in sines along one coordinate using the fast Fourier transform, and for each harmonic a tridiagonal system is solved by the Thomas algorithm. The cost is ∼N log N — nearly optimal. The price for the speed is narrow applicability: a rectangular domain, a uniform grid, constant λ and the same type of condition along each side.</p><h3>3.3 Iterative Methods</h3><p>In the two-dimensional problem direct methods are either expensive or require special conditions. Iterative methods, on the contrary, carry over from the first part almost unchanged: all they need is the formula “temperature at a node in terms of its neighbours”, and the matrix does not need to be stored at all — the temperature table Tᵢ,ⱼ itself is enough.</p><p>At interior nodes we use formula (3):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*B6SxdaTp7YCs2TtvjEKaUw.png" /></figure><p>At boundary nodes we use the formulas from Section 2.2, solved for the boundary node. For example, on the left side (j = 2, …, N_y − 1):</p><ul><li>first kind: T₁,ⱼ = T_L;</li><li>second kind: T₁,ⱼ = T₂,ⱼ + Δx q_L / λ;</li><li>third kind: T₁,ⱼ = (T₂,ⱼ + Bi<em>L T</em>∞L) / (1 + Bi_L).</li></ul><p>The other sides are handled the same way, with the inward-normal neighbour: T<em>{N_x−1, j} on the right, Tᵢ,₂ on the bottom, T</em>{i, N_y−1} on the top.</p><h4>3.3.1 Successive Over-Relaxation (SOR)</h4><p>As in the first part, we update the temperatures at all nodes, visiting them in numbering order: row by row from bottom to top, and within a row from left to right. A node is updated in two steps.</p><p><strong>Step 1 — the Gauss–Seidel value.</strong> When node (i, j) is reached, its left neighbour (i − 1, j) and bottom neighbour (i, j − 1) have already been updated in the current iteration, and their new values are used immediately:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_hP-typ8LhlILvvAzvGDGw.png" /></figure><p><strong>Step 2 — relaxation.</strong> The correction T̃ᵢ,ⱼ − Tᵢ,ⱼ⁽ᵏ⁾ is “amplified” with the relaxation parameter ω:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Ky7PvGe5VovO3iQRo3Qx_g.png" /></figure><p>With ω = 1 the second step changes nothing, and we get the <strong>Gauss–Seidel method</strong>. With ω &gt; 1 it is <strong>over-relaxation</strong>: the correction is made larger than Gauss–Seidel suggests, “with a margin”. In both cases all values are overwritten “in place” in a single array. Boundary nodes with second- and third-kind conditions are updated using the formulas above.</p><h3>Example for Our Problem</h3><p>Take the 4 × 4 plate from Section 2.4. The exact solution is T₂,₂ = T₃,₂ = 12.5, T₂,₃ = T₃,₃ = 37.5. We set the boundary values correctly from the start and take the interior ones as zero. For clarity we take ω = 1, i.e. the Gauss–Seidel method. The visiting order is T₂,₂ → T₃,₂ → T₂,₃ → T₃,₃:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YRSynKQObRo7vz9CsoDFWw.png" /></figure><p>where the right-hand sides always use the most recent values.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*442jAv1c0BoUeyevH7i2gg.png" /></figure><p>From the second iteration on, the error decreases by a factor of 4 per iteration. The symmetry is broken along the way: T₃,₂ ≠ T₂,₂ at intermediate iterations, because the nodes are visited from left to right. The method still arrives at the symmetric answer.</p><p>For a square grid with first-kind conditions, the optimal relaxation parameter is given by the same formula as for the rod:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kW6oCVFHP_c7fWxAzsOMHQ.png" /></figure><p>For our grid (N_x = 4), ω_opt = 2 / (1 + sin(π/3)) ≈ 1.072 — close to one, and the gain from relaxation is small: the error would decrease roughly 14-fold per iteration instead of 4-fold. On large grids the difference becomes enormous.</p><h3>Pitfall: Choosing ω</h3><p>The speed of SOR is very sensitive to ω, and erring on the low side is worse than erring on the high side: already at ω slightly below optimal, the number of iterations quickly grows towards that of Gauss–Seidel. With second- and third-kind conditions, a non-uniform grid or a complex domain shape, ω_opt is usually found experimentally: a few trial runs with different ω in the range 1.7–1.95 on a coarse grid.</p><h3>Pitfall: Parallelism</h3><p>Each node waits until its left and bottom neighbours have been updated, so the method cannot be parallelised directly. The way out is <strong>red-black ordering</strong>: colour the nodes in a checkerboard pattern (nodes with an even sum i + j are “red”, with an odd sum “black”). All four neighbours of a red node are black, and vice versa. So we can first update all red nodes simultaneously (using the black ones), and then all black nodes (using the already updated red ones). For the Laplace equation the convergence rate is the same as with the usual ordering, and ω_opt is the same.</p><h3>Algorithm</h3><p>Given: grid sizes N_x, N_y, boundary conditions on the four sides, initial guess T, relaxation parameter ω, tolerance ε, maximum number of iterations K. A single array T is needed.</p><p>Repeat for k = 0, 1, 2, …, K − 1:</p><ol><li>Set Δ = 0.</li><li>For each row j = 2, …, N_y − 1 and, within it, for each node i = 2, …, N_x − 1:</li></ol><ul><li>store the old value T_old = Tᵢ,ⱼ;</li><li>compute the Gauss–Seidel value from the current contents of the array:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*x-7fC73-kCTTcUnhvLPIAQ.png" /></figure><ul><li>write</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*svHNfKGVbAC5Y71TPJvDNw.png" /></figure><ul><li>update the change: Δ ← max(Δ, |Tᵢ,ⱼ − T_old|).</li></ul><p>3. Update the boundary nodes with second- and third-kind conditions (and include their change in Δ).</p><p>4. If Δ &lt; ε, stop: the answer is T.</p><p>If the tolerance is not reached within K iterations, stop and report it.</p><p>After finishing, the corner nodes can be assigned the average of the two adjacent boundary nodes (Section 2.2).</p><h4>3.3.2 Block (Line) Iterations</h4><p>In SOR (Section 3.3.1) a single node is treated as the unknown at each step, and all its neighbours are taken from the current approximation. Because of this, information propagates slowly: in one update a node learns only about its immediate neighbours. But in the first part we had a method that solves a whole chain of nodes at once and exactly — the Thomas algorithm. It can be embedded in an iterative method: at each step treat <strong>all nodes of one grid row</strong> as unknowns and take the adjacent rows from the current approximation. Information then propagates instantly along the row, and iterations are needed only for the coupling between rows.</p><p>Hence the name. Recalling the block form of the matrix from Section 2.3, a grid row is a single block B. Point methods update one unknown at a time, while line methods update one block at a time, so they are also called <strong>block</strong> methods: line Jacobi is block Jacobi, line Gauss–Seidel is block Gauss–Seidel for a block tridiagonal matrix.</p><h3>Equations for One Row</h3><p>Take row j (j = 2, …, N_y − 1). In equation (3), move the neighbours from rows j − 1 and j + 1 to the right-hand side and keep the neighbours within the row on the left:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*TJaNV6mpoHhriuC1EBWz3Q.png" /></figure><p>We sweep the rows from bottom to top, as in Gauss–Seidel: the lower row j − 1 has already been updated in the current iteration, the upper row j + 1 not yet. So the right-hand side is known:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3IGOJiAM0n4L6_aCsu0SMQ.png" /></figure><p>It is convenient not to eliminate the boundary nodes of the row T₁,ⱼ and T_{N_x, j}, but to include them in the system, as in the first part (Part 1, Section 2.1). Then for the row we get a tridiagonal system of the form (3) from Part 1</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*sXPrY4DNqg0l72f9VXLMNQ.png" /></figure><p>with coefficients:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tpOI0yEI3I1Kt5Rn7B2e3Q.png" /></figure><p>We solve it with the Thomas algorithm from Part 1 (Section 3.2.2). Note that the conditions on the left and right sides are now satisfied <strong>exactly</strong> at every iteration, rather than “catching up” with the solution with a lag, as in point methods.</p><p>With different steps, in the interior rows of the table</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*o4-Vi3k0ifLzQ-yXBjEEcA.png" /></figure><p><strong>Stability of the Thomas algorithm.</strong> In interior rows |bᵢ| = 4 &gt; |aᵢ| + |cᵢ| = 2: the diagonal dominance is strict, and by a wide margin (in the one-dimensional problem it was the equality |−2| = 1 + 1). Therefore the Thomas algorithm is stable for any boundary conditions at the ends of the row, even with second-kind conditions on both sides — the degeneracy seen in Part 1, Section 2.2 does not arise here.</p><p>The bottom and top sides (j = 1 and j = N_y) do not take part in the line solve. With first-kind conditions they simply do not change, and with second- and third-kind conditions they are updated after sweeping all rows, using the formulas from the beginning of Section 3.3.</p><h3>Example for Our Problem</h3><p>Take the 4 × 4 plate from Section 2.4 and line Gauss–Seidel (without relaxation). Each row has two unknowns, and the boundary nodes of each row are zero.</p><p>Row j = 2:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wco_MqaCoH_9S8zN3S_c-g.png" /></figure><p>Row j = 3 (the lower row is already new, the upper neighbours equal 100):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*UbYEfQb6KQO-y7UnhVtdBw.png" /></figure><p>Unlike point Gauss–Seidel, here the whole row is solved simultaneously, so the symmetry of the problem is preserved: T₂,ⱼ = T₃,ⱼ at every iteration. Let a = T₂,₂ = T₃,₂, c = T₂,₃ = T₃,₃. The system [4 −1; −1 4]·[x; x] = [d; d] gives 3x = d, so the iteration reduces to</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4d3VvgKuPzT5lNmElc7Y4w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8MpRYz_f2Q3YRF0z2IatUA.png" /></figure><p>From the second iteration on, the error decreases by a factor of 9 per iteration — for point Gauss–Seidel in Section 3.3.1 it was a factor of 4. After four iterations the error is 0.017 versus 0.39.</p><h3>What It Costs</h3><p><strong>One iteration.</strong> Per node: one addition for the right-hand side dᵢ plus the Thomas algorithm, about 8 operations (Part 1, Section 3.2.2). That is roughly twice as expensive as an iteration of a point method. But this can be almost entirely recovered. The coefficients aᵢ, bᵢ, cᵢ are the same for all rows and all iterations (if the boundary conditions do not vary along the left and right sides), so the denominators βᵢ and the Thomas coefficients Pᵢ need to be computed only <strong>once</strong> before the iterations. Each iteration then only has to recompute Rᵢ and perform the back substitution — about 4–5 operations per node.</p><p><strong>Number of iterations.</strong> On a square grid with equal steps, line Gauss–Seidel needs roughly <strong>half as many</strong> iterations as point Gauss–Seidel, and line SOR with optimal ω needs about √2 ≈ 1.4 times fewer than point SOR. The growth rate of the iteration count under grid refinement stays the same.</p><p>So on a square grid with Δx = Δy, the gain from line methods is modest: fewer iterations, but each is more expensive. The real benefit lies elsewhere.</p><h3>When It Really Pays Off: Different Steps</h3><p>Suppose the step in x is much smaller than the step in y: Δx ≪ Δy. This happens if the plate is elongated, if a thin boundary layer has to be resolved in x, or if the conductivity in x is much larger than in y (an anisotropic material has the same effect). In the equation for a node the neighbour weights are 1/Δx² in x and 1/Δy² in y, so the x-coupling is (Δy / Δx)² times stronger.</p><p>This is bad for point methods. A node is determined almost entirely by its x-neighbours, while information along x still advances by one node per iteration. The iteration count of point methods is governed by the <strong>small</strong> step Δx, even if there are very few nodes in y.</p><p>A line method with Thomas solves along x handles the strong coupling exactly, leaving only the weak coupling between rows to the iterations. Its iteration count is governed by the <strong>large</strong> step Δy. The gain in iteration count is of order (Δy / Δx)²: for Δy = 10 Δx that is about 100 times.</p><p>Hence the rule: <strong>the line solves run along the direction of stronger coupling</strong>, i.e. where the step is smaller (or the conductivity larger). If Δy ≪ Δx, columns rather than rows should be solved: everything is the same with i ↔ j swapped.</p><h3>Sweep Order and Parallelism</h3><p>As with point Gauss–Seidel, each row waits until the row below it has been updated. The remedy is analogous to the red-black ordering from Section 3.3.1 — the <strong>“zebra”</strong> ordering: first solve all rows with even j (they depend only on odd rows and not on each other, so they can be solved in parallel), then all rows with odd j using the already updated even rows.</p><h3>Alternating Directions: the ADI Method</h3><p>If the coupling is equally strong in both directions (or the stronger direction differs between parts of the domain), it is natural to alternate: solve along rows for one half of the iteration and along columns for the other. This is how the <strong>alternating direction implicit method</strong> (ADI, the Peaceman–Rachford method) works. In the Kronecker notation (4) of Section 2.3 the matrix is a sum of two parts: A = H + V, where H = Iₘ ⊗ Kₙ accounts for couplings along rows and V = Kₘ ⊗ Iₙ along columns. An iteration consists of two half-steps:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*bFgOtJfsuPDuo0pLHoGz_g.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4QmVFmXNToYBnngXlmM8wg.png" /></figure><p>where r &gt; 0 is an iteration parameter. The matrix rI + H splits into independent tridiagonal systems along rows, and rI + V along columns, so each half-step is a set of Thomas solves.</p><p>With a single constant r the iteration count grows like N_x, as for SOR with ω_opt. But if r is cycled through several specially chosen values (from small ones that damp the smooth error components to large ones that damp the “jagged” ones), the iteration count grows only like log N_x. Choosing the parameters is a separate topic; for a rectangle with first-kind conditions it is well studied.</p><h3>Algorithm (Line SOR, Solves Along Rows)</h3><p>Given: grid sizes N_x, N_y, steps, boundary conditions, initial guess T, relaxation parameter ω (ω = 1 is line Gauss–Seidel), tolerance ε, maximum number of iterations K.</p><p><strong>Preparation.</strong> Build the row coefficients aᵢ, bᵢ, cᵢ from the table above and perform the part of the Thomas forward sweep that does not depend on the right-hand side:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ViqDPWjzpGZqCovYHxpvKw.png" /></figure><p>Repeat for k = 0, 1, 2, …, K − 1:</p><ol><li>Set Δ = 0.</li><li>For each row j = 2, …, N_y − 1 (bottom to top):</li></ol><ul><li>build the right-hand side dᵢ from the table: at interior nodes dᵢ = Tᵢ,ⱼ₋₁ + Tᵢ,ⱼ₊₁ (the lower row is already new, the upper one still old);</li><li>forward sweep for Rᵢ only:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dxp4TDsK_c5-djvwkRpeaA.png" /></figure><ul><li>back substitution — the Gauss–Seidel solution of the row:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*oROvUDYyIPFFk9MRbsCfBw.png" /></figure><ul><li>for each node of the row i = 1, …, N_x, apply relaxation and update the change:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*l-7_5AR4hNUeusdE4B6aPQ.png" /></figure><p>3. Update the bottom and top sides with second- and third-kind conditions (and include their change in Δ).</p><p>4. If Δ &lt; ε, stop: the answer is T.</p><p>If the tolerance is not reached within K iterations, stop and report it.</p><h4>3.3.3 Stopping Criterion</h4><p>The same criteria as in the first part are used: the change in the solution per iteration, or the residual</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NOdRT3EufnCCkdX268mpHw.png" /></figure><p>(how far equation (3) is from being satisfied):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*EASO8oK7_yIltcIuH0lAfw.png" /></figure><p>In the two-dimensional problem Tᵢ,ⱼ may change slowly, so the stopping criterion may terminate the process earlier than it should. Therefore:</p><ul><li>it is worth comparing values not every iteration but every few iterations;</li><li>for slow methods the threshold ε should be chosen with a large margin;</li><li>it is convenient to normalise the residual by its initial value: max |r⁽ᵏ⁾| / max |r⁽⁰⁾| &lt; ε, so that the criterion does not depend on the temperature scale;</li><li>when debugging, it is useful to compare with a direct-method solution on a small grid.</li></ul><p>Keep in mind, too, that even an exactly solved linear system differs from the solution of equation (1) by the discretisation error ∼h². Solving the system much more accurately than this error is pointless.</p><h3>3.3.4 Other Iterative Methods</h3><p>In the first part these methods were mentioned “for the future” (Section 3.3.6). In the two-dimensional problem they become the main ones.</p><ul><li><strong>Conjugate gradient method (CG)</strong> — requires a symmetric positive definite matrix, and our matrix (after eliminating first-kind boundary nodes, Section 2.3) is exactly that. The iteration count grows like N_x, as for SOR with ω_opt, but no parameter needs to be tuned.</li><li><strong>Preconditioned CG (PCG)</strong> — with incomplete Cholesky factorisation (IC, MIC) the iteration count drops several-fold.</li><li><strong>Multigrid method</strong> — a few (red-black) Gauss–Seidel iterations damp the “jagged” error, and the smooth error is transferred to a grid twice as coarse. The iteration count (usually around ten) does not depend on the grid size, and the total work is O(N). For the Laplace equation on a rectangle this is the benchmark method.</li></ul><h3>4. Conclusion</h3><p>In the two-dimensional case the number of unknowns grows like N_x², and dense direct methods become impractical already on modest grids.</p><p>Direct methods for sparse matrices run into <strong>fill-in</strong>: during elimination, zeros inside the band turn into nonzero entries. The elimination order of the unknowns determines how much fill-in there will be.</p><p>Iterative methods barely change in the transition from a rod to a plate: at each node, the average of the neighbours. But the iteration count of Jacobi and Gauss–Seidel grows like N_x², so in practice SOR, preconditioned CG or multigrid are used.</p><p>The Thomas algorithm from the first part does not disappear: it remains a working tool inside line iterations, ADI and fast methods.</p><p>MATLAB/Octave code for the example from section 2.4 on a 100 × 100 grid (solved with SOR, the direct method A \ b, and conjugate gradients with an ichol preconditioner): <a href="https://github.com/Semen1996/steady-state-heat-2d">repository link</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2278cb439dd2" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solving the Steady-State Heat Equation, Part 1: The 1D Rod]]></title>
            <link>https://medium.com/@semen.tolstoguzov96/solving-the-steady-state-heat-equation-part-1-the-1d-rod-7d9fec900591?source=rss-01347f1bf6b0------2</link>
            <guid isPermaLink="false">https://medium.com/p/7d9fec900591</guid>
            <category><![CDATA[thermodynamics]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[physics]]></category>
            <category><![CDATA[numerical-methods]]></category>
            <dc:creator><![CDATA[Simon]]></dc:creator>
            <pubDate>Mon, 19 Oct 2026 12:37:54 GMT</pubDate>
            <atom:updated>2026-10-19T12:37:54.313Z</atom:updated>
            <content:encoded><![CDATA[<p>If the ends of a rod are held at constant temperatures, the temperature distribution along it can be found without a computer: it is linear. So why solve this problem numerically? Make it just a little more complicated — let heat be generated only in part of the rod, or move from a rod to a plate — and there is no longer a simple analytical solution, so numerical methods become necessary. The one-dimensional problem is a convenient testing ground: the methods are easy to understand on it, and the answer is known in advance, so each method can be checked.</p><p>In this article we will go all the way from the heat equation and boundary conditions, through the finite difference method, to a system of linear algebraic equations (SLAE). Then we will look at how to solve it: with direct methods (Gaussian elimination and the tridiagonal matrix algorithm) and iterative methods (Jacobi, Gauss–Seidel, successive over-relaxation). The main methods are worked through on examples that can be computed by hand, with cost estimates and pitfalls.</p><h3>1. Description</h3><p>Heat conduction is the molecular transfer of heat in a continuous medium. This process arises when the temperature distribution is non-uniform.</p><p>Unsteady heat transfer by conduction is described by the following equation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/374/1*XnkpZjzWt57WZZ9xe2s5iQ.png" /></figure><p>where ρ is the density, c is the specific heat capacity, λ is the thermal conductivity, and Q is the power of internal heat sources.</p><p>If the boundary conditions and sources do not change in time, then after a sufficiently long time the temperature stops changing: ∂T/∂t = 0. What remains is the <strong>steady-state heat equation</strong>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/277/1*thBa6-C0pTiM6B-MCrI6gg.png" /></figure><p>For constant λ this is the <strong>Poisson equation</strong>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/343/1*IezVbqbesayEAKiwUaIErA.png" /></figure><p>and in the absence of sources (Q = 0) it is the <strong>Laplace equation</strong> (this is the case we will consider from here on)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/302/1*0vn-KKAQW41H7D_v5Qg50w.png" /></figure><p>Equation (1) describes a multitude of possible heat conduction processes. To select one of these countless variants and give it a complete mathematical description, relation (1) must be supplemented with uniqueness conditions, which include geometric, physical, initial and boundary conditions.</p><ul><li><strong>Geometric conditions</strong> define the shape and size of the body in which the process takes place.</li><li><strong>Physical conditions</strong> define the thermophysical properties of the body λ, ρ, c (not needed in our case).</li><li><strong>Time (initial) conditions</strong> contain the temperature distribution in the body at the initial moment (not needed in our case).</li><li><strong>Boundary conditions</strong> define how the process behaves on the surface of the body and can be specified in several ways.</li></ul><h3>1.1 Boundary conditions</h3><p><strong>Boundary conditions of the first kind (Dirichlet)</strong> — the temperature distribution on the surface (or boundary) of the body is specified:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/151/1*ptt9cXLbPQu6iJ3d5IQpnw.png" /></figure><p>where T_w is the temperature on the surface of the body.</p><p><strong>Boundary conditions of the second kind (Neumann)</strong> — the heat flux is specified at every point of the surface (or boundary) of the body:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/277/1*NYqm9ijCBYliZsJgdxS27w.png" /></figure><p>where n is the normal to the surface of the body.</p><p><strong>Boundary conditions of the third kind</strong> — a relationship is specified between the conductive heat flux from the solid wall and the heat flux to the surrounding medium driven by the temperature difference (Newton’s law of cooling)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/399/1*beGPUK-LjbdkAaIAo3hfMA.png" /></figure><p>where α is the heat transfer coefficient and T_∞ is the ambient temperature.</p><p><strong>Boundary conditions of the fourth kind</strong> — to describe the thermal interaction between elements with different thermophysical properties, equality of temperatures and heat fluxes on both sides of the interface is required:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/456/1*PZ5fZ-tRIrcMX_JCpdkYDA.png" /></figure><p>where b is the interface between the media; T₁, T₂ are the temperatures of the media in contact. This condition is used, for example, when solving heat conduction problems for multilayer plates.</p><p>The differential equation (1) together with the uniqueness conditions gives a complete mathematical formulation of the heat conduction boundary value problem.</p><h3>2. Finite difference method</h3><p>We will solve equation (1) with the corresponding boundary conditions numerically. The method most often used for solving partial differential equations is the <strong>finite difference method</strong>. The solid body is represented as a set of nodes. By approximating the partial derivatives of the differential equation (1) with finite differences, one obtains a system of linear algebraic equations for the temperature as a local quantity at each grid node. The resulting system is not closed; to close it, a difference representation of the boundary conditions is used. The result is a closed system of linear algebraic equations, which is solved numerically.</p><h3>2.1 The one-dimensional case</h3><p>Consider a rod of length L. Divide it along its length into Nₓ − 1 equal intervals</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/818/1*2j953yYHRwEyYo4KPXf5BA.png" /></figure><p>In the one-dimensional case, the heat equation (1) takes the form:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/172/1*V3DGwB015SxiS4iBCy94rQ.png" /></figure><p>Replacing the differential operator with its finite difference analogue, we get:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/841/1*HcaA_RUAc2_OhsRrxosESQ.png" /></figure><p>where i is the node index, Nₓ is the number of grid nodes, and Δx is the grid spacing in x. T₁ and T_Nₓ are determined from the boundary conditions:</p><ul><li>Boundary conditions of the first kind</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/344/1*LDNY78YjUPNHzbXLq26wNQ.png" /></figure><ul><li>Boundary conditions of the second kind</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/619/1*qxlrfWwg3GDSGuj3myiPNg.png" /></figure><ul><li>Boundary conditions of the third kind</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/953/1*y6BH88CN38PrsDLdmqyzYA.png" /></figure><p>where Bi = α·Δx/λ.</p><p>As a result, we obtain a <strong>system of linear algebraic equations (SLAE)</strong>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/151/1*u8_JbDCoaEgIE5KFUH3osA.png" /></figure><p>where A is the coefficient matrix, T is the vector of unknowns, and b is the right-hand side vector. <strong>For boundary conditions of the first kind</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/241/1*zVvlym2ULaeGUBrwA7WA8w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/194/1*p-8m5LmX4m4Zrf4ttPiLvw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/421/1*oxhzunZoywEolVXYQjMyIg.png" /></figure><h3>2.2 Analytical solution</h3><p>Before solving the system, note that our problem has an exact solution. Integrating the equation d²T/dx² = 0 twice, we get a linear function</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/276/1*UOR2Q-WE1vNP1KSzNjEhVg.png" /></figure><p>We find C₁ and C₂ from the boundary conditions of the first kind: T(0) = T_L gives C₂ = T_L, and T(L) = T_R gives C₁ = (T_R − T_L)/L. So the temperature varies linearly along the rod:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/391/1*JrNMtkfxjvo2uqKCd4MV5A.png" /></figure><p>This solution can be used as a <strong>reference</strong> for comparison with the numerical results.</p><p>With boundary conditions of the second kind at both ends, the constants cannot be found this way. The flux determines only the slope dT/dx = C₁, while the temperature level C₂ remains free: the solution is determined only up to a constant (physically, only the flux is specified, not the temperature level). Moreover, both conditions specify the same slope, so the fluxes at the ends must be consistent: as much heat as enters the rod must leave it, otherwise there is no steady-state solution at all. Therefore, a condition of the first or third kind must be specified on at least one boundary.</p><p>One question remains: how do we solve the resulting system of equations? We will look at this in the next section.</p><h3>3. Solving the SLAE</h3><p>Methods for solving SLAEs fall into two large groups:</p><ul><li><strong>direct (exact)</strong> — give the solution in a finite number of arithmetic operations known in advance (Gaussian elimination, the tridiagonal matrix algorithm);</li><li><strong>iterative</strong> — build a sequence of approximations T⁽⁰⁾, T⁽¹⁾, … that converges to the exact solution (Jacobi, Gauss–Seidel, successive over-relaxation).</li></ul><p>The choice of method is determined by the structure of the matrix A, so let us first look at its properties.</p><h3>3.1 Matrix properties</h3><p>Let us write each equation of the system in general form:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/795/1*ko4xB4ywUUQXQb_NcMzIaA.png" /></figure><p>where a₁ = 0 and c_Nₓ = 0 (the first node has no left neighbour, the last has no right one), and dᵢ are the components of the right-hand side vector. For interior nodes, from (2): aᵢ = 1, bᵢ = −2, cᵢ = 1, dᵢ = 0. For boundary conditions of the first kind: b₁ = 1, c₁ = 0, d₁ = T_L and a_Nₓ = 0, b_Nₓ = 1, d_Nₓ = T_R.</p><p>This reveals three important properties of the matrix A:</p><ol><li><strong>Tridiagonality</strong> — non-zero elements appear only on the main diagonal and the two diagonals adjacent to it.</li><li><strong>Sparsity</strong> — out of Nₓ² elements, at most 3Nₓ are non-zero. For example, with Nₓ = 1000 this is ≈ 3000 non-zero elements out of 1⁰⁶. Storing such a matrix in full and solving the system “head-on” is wasteful.</li><li><strong>Diagonal dominance</strong> — the absolute value of the diagonal element is not less than the sum of the absolute values of the other elements in the row:</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/250/1*_RPvaP7q-YwpfgZezsbbBg.png" /></figure><p>n interior rows equality holds (|−2| = |1| + |1|), while in rows with boundary conditions of the first and third kind the inequality is strict. This property guarantees the stability of the tridiagonal matrix algorithm and the convergence of the Jacobi and Gauss–Seidel iterative methods.</p><h3>3.2 Direct methods</h3><h3>3.2.1 Gaussian elimination</h3><p>The idea of the method is the same as in school: eliminate the unknowns one by one until a single equation with a single unknown remains. Solve it, and then find the rest in turn.</p><p><strong>A simple example</strong></p><p>Let us solve a system of three equations:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/356/1*zLbvdVSy16Gtjr9TuZos8g.png" /></figure><p><strong>Step 1 — eliminate x from equations (2) and (3).</strong> Subtract twice (1) from (2), and subtract (1) from (3):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/268/1*Ex-aQz6kp4--E3NLOyC6ug.png" /></figure><p><strong>Step 2 — eliminate y from the last equation.</strong> Subtract the second equation from it:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/268/1*FFaeGNP2xusmJi9ecjLcGg.png" /></figure><p>The system has taken a “staircase” form (<strong>triangular form</strong>): the last equation has one unknown, the one before it has two, and so on.</p><p><strong>Step 3 — find the unknowns from the bottom up:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/754/1*zmJx2UunLKHY__7mPR7k5g.png" /></figure><p>Steps 1–2 are called <strong>forward elimination</strong> (reducing the system to the staircase), and step 3 is <strong>back substitution</strong> (finding the unknowns from the bottom up). This is Gaussian elimination.</p><p><strong>The same in matrix notation</strong></p><p>There is no need to write the letters x, y, z — a table of coefficients with the right-hand side appended on the right (the <strong>augmented matrix</strong>) is enough. All operations are performed on the rows of this table.</p><p>There is a single rule: to get a zero below the diagonal, subtract from the row the row containing the diagonal element (called the <strong>pivot</strong>), multiplied by</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/393/1*ONazj7NhTu2Pt-t5SjdY6Q.png" /></figure><p>Proceed column by column from left to right until only zeros remain below the diagonal.</p><p><strong>Example for our problem</strong></p><p>Take a rod with Nₓ = 4 nodes, T_L = 100, T_R = 40:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/368/1*NUi7AFXumYZp_KhRWMptwA.png" /></figure><p><strong>Column 1.</strong> The pivot is 1. A zero is needed only in the second row: subtract the first row from it (m = 1/1 = 1). The third and fourth rows already have zeros there.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/391/1*tu9O_VJ2iwg-mEEAtdIrzA.png" /></figure><p><strong>Column 2.</strong> The pivot is −2. A zero is needed in the third row: m = 1/(−2) = −½, i.e. add half of the second row to the third (subtract from the third row the second row multiplied by −½).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/399/1*g_oPYFkU5LV23Mb4k1S7NA.png" /></figure><p><strong>Column 3.</strong> There is already a zero below the diagonal — nothing to do. The staircase is ready.</p><p><strong>Back substitution</strong> — read the rows from the bottom up:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Sb1l4BusLOXuq8OY8EFo6w.png" /></figure><p>We obtained the linear profile 100, 80, 60, 40 — as expected (section 2.2).</p><p>Note: almost all of the operations came down to “subtract a row multiplied by zero”, i.e. doing nothing. Gaussian elimination does not know this and dutifully goes through every element. The tridiagonal matrix algorithm (section 3.2.2) is the same Gaussian elimination that knows in advance where the zeros are and skips them.</p><p><strong>How much it costs</strong></p><p>To zero out one column, almost all rows have to be processed, and in each row almost all elements. There are N columns, N rows and N elements per row — on the order of N³ operations in total (more precisely, ⅔N³). Back substitution is much cheaper — on the order of N².</p><p>For N = 1000 nodes this is about 7·10⁸ operations.</p><p><strong>Pitfall: the pivot</strong></p><p>We have to divide by the pivot. If it is zero, the method breaks down even though a solution exists. For example:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/235/1*VPHVyRyjM5ubHJn20PB6pQ.png" /></figure><p>The first row cannot be used to eliminate x — its coefficient of x is zero. The fix is simple: <strong>swap the rows</strong>, and everything works.</p><p>A similar problem occurs if the pivot is not zero but very small: then m becomes huge and rounding errors spoil the answer. Therefore, programs usually choose, at every step, the row with the <strong>largest absolute value</strong> element in the current column and put it in the pivot position (<strong>partial pivoting</strong>).</p><p>For our matrix this is unnecessary: it is diagonally dominant (section 3.1), and the pivots never become small.</p><p><strong>Algorithm</strong></p><p>Given: an N × N matrix A and a right-hand side column b.</p><p><strong>Forward elimination</strong> — repeat for each column k = 1, 2, …, N−1:</p><ol><li>Take the pivot a_kk (on the diagonal in the k-th column).</li><li><em>(If pivoting is needed.)</em> In the k-th column, starting from row k and below, find the row p with the largest absolute value element:</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/263/1*RfgOOW1968ofYrUx5BQ3Wg.png" /></figure><p>and swap rows p and k — together with the right-hand side elements b_p and b_k.</p><p>3. For each row i below the pivot row (i = k+1, …, N):</p><p>3.1. compute the multiplier</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/194/1*JU8AhgBJSJAQZsZ85praaA.png" /></figure><p>3.2. subtract from the i-th row of the matrix the k-th row multiplied by m_ik:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/524/1*bzjZNDwsI8pL4D-zJK-6MA.png" /></figure><p>3.3. do the same with the right-hand side:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/259/1*zqpWIy_FLbg25s-4YfMtsA.png" /></figure><p>After this, there are zeros below the diagonal — the system has a staircase form:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/423/1*79NX-nrxc06gYcsd_7tklg.png" /></figure><p>(here a_ij and b_i are the values already modified by forward elimination).</p><p><strong>Back substitution</strong> — repeat for rows i = N, N−1, …, 1 (from the bottom up):</p><ol><li>Take the right-hand side b_i.</li><li>Subtract from it the contribution of the already found unknowns T_{i+1}, …, T_N:</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/734/1*nOqD4vl8DfFSYML2O2ojWg.png" /></figure><p>The unknowns T₁, …, T_{i−1} do not appear in the i-th equation: after forward elimination there are zeros to the left of the diagonal. For the last row (i = N) there is nothing to subtract: s_N = b_N.</p><p>3. Divide the result by the diagonal element:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/167/1*zGGsLqjexnoRMHLXsW-Nbw.png" /></figure><p>Combining the steps, we get:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/868/1*DP7JLZEfYlaJcvru40OZUg.png" /></figure><p>Result: the vector T = (T₁, …, T_N)ᵀ.</p><h3>3.2.2 Tridiagonal matrix algorithm (Thomas algorithm)</h3><p>In our system, each equation links only three neighbouring unknowns: T<em>{i−1}, T_i and T</em>{i+1}. Therefore, from the first equation we can express T₁ in terms of T₂, substitute it into the second and express T₂ in terms of T₃, and so on to the end. The last equation will contain a single unknown, and then we can go back and find all the others in turn. The unknown is, as it were, “swept” along the chain and back, which is why the method is also called the <strong>sweep method</strong>.</p><p><strong>A simple example</strong></p><p>Let us solve a system in which each equation contains at most three neighbouring unknowns:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/327/1*7qVmZgDdpOw0mBiZK56XGQ.png" /></figure><p><strong>Step 1 — express x in terms of y</strong> from equation (1):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/177/1*xa_UASExrTHKg5Oc4h4bIg.png" /></figure><p><strong>Step 2 — substitute into (2) and express y in terms of z:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/535/1*9ahaL-5nDAyhprcxLnL_Lw.png" /></figure><p><strong>Step 3 — substitute into (3).</strong> Only one unknown remains:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/434/1*jt5zKiGrNfb5tMyESjmi4g.png" /></figure><p><strong>Step 4 — go back</strong>, substituting what we found into the expressions already obtained:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/615/1*1S6g4fTC8RQk8MwiGPIH6g.png" /></figure><p>Steps 1–3 are called the <strong>forward sweep</strong>: we go from left to right and obtain expressions of the form “x in terms of y”, “y in terms of z”. Step 4 is the <strong>backward sweep</strong>: we go from right to left and find the unknowns.</p><p>This is the same Gaussian elimination (section 3.2.1): substituting x into (2) is the same as eliminating x from (2). The difference is that the sweep does not waste time on zeros: in each equation it works with only three coefficients.</p><p><strong>The same in general form</strong></p><p>Write the system in the form (3):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/623/1*zWWqiIGDrkZFDjl3KCyqLg.png" /></figure><p>where a₁ = 0 (there is nothing to the left of the first node) and c_N = 0 (nor to the right of the last). In the example a = (0, 1, 1), b = (1, 2, 2), c = (1, 1, 0), d = (3, 8, 8).</p><p>In the forward sweep, every expression has the same form: “the previous unknown in terms of the next one”:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/437/1*A44jC-qHyA1I3xl6kizvpA.png" /></figure><p>where P_i and R_i are numbers called the <strong>sweep coefficients</strong>. In the example x = −1·y + 3, i.e. P₁ = −1, R₁ = 3; y = −1·z + 5, i.e. P₂ = −1, R₂ = 5.</p><p><strong>Where the formulas come from.</strong> Suppose the expression for T<em>{i−1} is already known: T</em>{i−1} = P<em>{i−1}·T_i + R</em>{i−1}. Substitute it into the i-th equation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/546/1*ljSUrFhHjJIRsEcGDQkDzA.png" /></figure><p>Collect the terms with T_i on the left:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/586/1*4X9Ks0Wn8kOP4Zwh17WdSg.png" /></figure><p>Denote the denominator β<em>i = b_i + a_i·P</em>{i−1} and divide by it. We get an expression of the form (4) with coefficients</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/487/1*EYpwZgvP3ioqFnb__Ohf8A.png" /></figure><p>For the first equation there is no previous unknown (a₁ = 0), so β₁ = b₁:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/376/1*9Yc3VAZFiGNaGJpM4uxc0w.png" /></figure><p>In the last equation there is no next unknown (c_N = 0), so P_N = 0 and immediately T_N = R_N. This is where the backward sweep starts.</p><p>Let us check on the example:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/631/1*w78ERK87AmYNrtb6N1znGQ.png" /></figure><p>Backward sweep: T₃ = R₃ = 3, T₂ = −1·3 + 5 = 2, T₁ = −1·2 + 3 = 1. We obtained the same answer.</p><p><strong>Example for our problem</strong></p><p>Take a rod with Nₓ = 4 nodes, T_L = 100, T_R = 40 (as in section 3.2.1). Row coefficients:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/540/1*iLdv25oOhX4n4cCe8g20Ww.png" /></figure><p><strong>Forward sweep:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/837/1*OfFqdYShxaeBClbs_3Eswg.png" /></figure><p><strong>Backward sweep:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*IjLzUcfWUo2f1atet9-mRw.png" /></figure><p>We obtained the same linear profile 100, 80, 60, 40.</p><p>Compare the denominators β_i with the pivots in the example from section 3.2.1: they were also 1, −2, −3/2, 1. The sweep performs the same operations as Gaussian elimination, only it skips the zeros.</p><p><strong>How much it costs</strong></p><p>The forward sweep spends about six operations per node (one addition and one multiplication for β_i, a division for P_i, a multiplication, a subtraction and a division for R_i), and the backward sweep two. That is about 8N operations in total, i.e. O(N).</p><p>For N = 1000 nodes this is about 8·10³ operations versus 7·10⁸ for Gaussian elimination.</p><p>Memory is also O(N): only the three diagonals a, b, c, the right-hand side d and the coefficients P, R are stored. The N × N matrix itself does not need to be stored.</p><p>For the one-dimensional problem this is the optimal method: it is impossible to do better than O(N), because each of the N unknowns has to be computed at least once.</p><p><strong>Pitfall: division by β_i</strong></p><p>As in Gaussian elimination, each step involves a division, here by β_i. If β_i = 0, the method breaks down, and if β_i is very small, rounding errors grow. Swapping rows as in Gaussian elimination is not allowed here: it would destroy the tridiagonal structure.</p><p>Fortunately, with <strong>diagonal dominance</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/242/1*i_7rm5UWgKhEpPAl_nsWOg.png" /></figure><p>(strict in at least one row) this does not happen. Let us show that then |P<em>i| ≤ 1. Suppose |P</em>{i−1}| ≤ 1. Then</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/922/1*qVAV7VC_unIahU3OuRsu5Q.png" /></figure><p>The denominator is not less than |c_i|, the coefficients P_i do not grow, and rounding errors do not accumulate.</p><p>Our matrix satisfies this condition (section 3.1): in interior rows |−2| = 1 + 1, and in rows with boundary conditions of the first kind |1| &gt; 0.</p><blockquote><em>With conditions of the second kind at both ends, the last denominator turns out to be β_N = 0. The product of all β_i equals the determinant of the matrix, so the matrix is singular — this is the same non-uniqueness of the solution discussed in section 2.2.</em></blockquote><p><strong>Algorithm</strong></p><p>Given: coefficients a_i, b_i, c_i and right-hand sides d_i, i = 1, …, N, with a₁ = 0, c_N = 0.</p><p><strong>Forward sweep</strong> — compute the sweep coefficients from left to right:</p><ol><li>For the first row:</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/376/1*9Yc3VAZFiGNaGJpM4uxc0w.png" /></figure><p>2. For each row i = 2, …, N:</p><p>2.1. compute the denominator</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/260/1*IE2kxViy3EeLE9N3pe3_Hw.png" /></figure><p>2.2. compute</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/186/1*bT-EjdYXhxpGDMmWAWV4Cg.png" /></figure><p>2.3. compute</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/285/1*vYd-ECy3_4tAXyOga_r4wQ.png" /></figure><p><strong>Backward sweep</strong> — compute the temperatures from right to left:</p><ol><li>For the last row P_N = 0, so</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/177/1*ThzbMYHFH-ZtNO4nufQMqg.png" /></figure><p>2. For each row i = N−1, …, 1:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/277/1*x-zbJmG9C5fj2kWG-UwPjA.png" /></figure><p>Result: the vector T = (T₁, …, T_N)ᵀ.</p><h3>3.2.3 Other direct methods</h3><p>For the one-dimensional problem the sweep is optimal. There are other direct methods worth knowing, since they come up in the literature.</p><ul><li><strong>LU decomposition</strong> (PA = LU, L is lower triangular, U is upper triangular, P is a row permutation) — Gaussian elimination with the multipliers stored. It costs the same (~⅔N³), but then each new right-hand side is solved in O(N²). Beneficial when there is one matrix and many right-hand sides (an implicit scheme in an unsteady problem). The sweep is its special case for a tridiagonal matrix.</li><li><strong>Cholesky decomposition</strong> (A = LLᵀ) — a variant of LU for symmetric positive definite matrices, twice as cheap (~⅓N³) and requiring no pivoting. Our matrix becomes such a matrix if the boundary nodes with first-kind conditions are eliminated and the equations are multiplied by −1: the result is tridiag(−1, 2, −1).</li><li><strong>LDLᵀ decomposition</strong> — a variant of Cholesky for symmetric but not necessarily positive definite matrices (D is diagonal). It requires no square roots.</li><li><strong>QR decomposition</strong> (A = QR, Q is orthogonal) — the most stable, but roughly twice as expensive as LU. Used mainly in least-squares problems. Overkill for our well-conditioned matrices.</li><li><strong>Sparse LU and Cholesky.</strong> In 2D/3D the main problem is not the number of operations but <strong>fill-in</strong>: L and U contain many more non-zero elements than A. Therefore, before factorization the unknowns are reordered (AMD, nested dissection algorithms) to reduce fill-in.</li></ul><h3>3.3 Iterative methods</h3><p>In the one-dimensional case, the sweep solves the problem exactly and quickly. In two and three dimensions each node already has four and six neighbours, the sweep is not directly applicable, and Gaussian elimination and LU decomposition require a lot of memory and time. That is when iterative methods are used. Let us look at them on the one-dimensional problem, where they are easy to understand.</p><p>All iterative methods share one idea: take some approximation to the solution T⁽⁰⁾ (for example, zero or linear between the boundary values) and improve it step by step using the same rule. This gives a sequence T⁽⁰⁾, T⁽¹⁾, T⁽²⁾, … that approaches the exact solution. k is the <strong>iteration</strong> number.</p><p>For iterative methods, it is convenient to write each equation from section 2.1 in the form “temperature at a node in terms of its neighbours”. At interior nodes, from (2) we get</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/728/1*BmSh-XU_PSS2psP9SGZf7A.png" /></figure><p>i.e. the temperature at a node equals the <strong>arithmetic mean</strong> of its neighbours’ temperatures. At boundary nodes, for example at the left end:</p><ul><li>first kind: T₁ = T_L;</li><li>second kind: T₁ = T₂ + Δx·q_L/λ;</li><li>third kind: T₁ = (T₂ + Bi<em>L·T</em>∞) / (1 + Bi_L).</li></ul><p>At the right end the neighbour is T_{Nₓ−1}, and the formulas are obtained from section 2.1 in exactly the same way.</p><h3>3.3.1 Jacobi method</h3><p>Recompute the temperatures at all nodes using the formulas above, substituting the <strong>old</strong> values of the neighbours into the right-hand sides. We get a new approximation and repeat.</p><p><strong>A simple example</strong></p><p>Let us solve the system</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/273/1*SnRWP8mGXyIKUL_2HW1Csg.png" /></figure><p>Its exact solution is x = 1, y = 2.</p><p>Express x from (1) and y from (2):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/396/1*K8rOdREhZlIo9tMVqaopfA.png" /></figure><p>Start with x = 0, y = 0 and substitute the values from the previous row of the table into the right-hand sides:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/848/1*gbonVDtdN-RIazbdft6UCg.png" /></figure><p>The approximations oscillate around the answer (1, 2) and get closer to it with each iteration. We will not get the exact answer in a finite number of steps, but we can get arbitrarily close to it. This is the main difference from direct methods.</p><p><strong>Formulas for our problem</strong></p><p>At interior nodes, the new temperature is the mean of the <strong>old</strong> temperatures of the neighbours:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/620/1*dEHXTttl9DDumGjVL6oWPA.png" /></figure><p>At boundary nodes — the formulas from the beginning of the section, also with the old value of the neighbour:</p><ul><li>first kind: T₁⁽ᵏ⁺¹⁾ = T_L (the boundary value does not change);</li><li>second kind: T₁⁽ᵏ⁺¹⁾ = T₂⁽ᵏ⁾ + Δx·q_L/λ;</li><li>third kind: T₁⁽ᵏ⁺¹⁾ = (T₂⁽ᵏ⁾ + Bi<em>L·T</em>∞) / (1 + Bi_L).</li></ul><p>It is important that all new values are computed <strong>from the old ones only</strong>. Therefore two arrays are needed: the old T⁽ᵏ⁾ and the new T⁽ᵏ⁺¹⁾. If the new values are written directly into the old array, the result is a different method — the Gauss–Seidel method (below).</p><p><strong>Example for our problem</strong></p><p>Take a rod with Nₓ = 4 nodes, T_L = 100, T_R = 40 (as in section 3.2.1). The exact solution is 100, 80, 60, 40. Set the boundary values correctly right away and take the interior ones as zero: T⁽⁰⁾ = (100, 0, 0, 40). At the interior nodes</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/638/1*_hOPdKGNz0UuhwG0NCBIFg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/518/1*XmulX981em0IJYO5MMTvQA.png" /></figure><p>The error is <strong>exactly halved</strong> with each iteration. To get, for example, an error below 10⁻⁶, about 27 iterations are needed. Physically this resembles heat gradually “seeping” from the hot and cold ends into the rod.</p><p><strong>How much it costs</strong></p><p><strong>One iteration</strong> is cheap: one addition and one division by 2 per node, about 2Nₓ operations in total, i.e. O(Nₓ).</p><p><strong>The number of iterations</strong> depends on how much the error is reduced per iteration. At Nₓ = 1000 the Jacobi method turns out to be slower than even Gaussian elimination (7·1⁰⁸). For the one-dimensional problem it is impractical. But it is very simple, and in 2D/3D it takes little memory and parallelizes easily: all nodes are computed independently of one another.</p><p><strong>Why it is so slow.</strong> In one iteration a node learns only about its immediate neighbours. Information about a boundary value advances by one node per iteration, and just to reach the middle of the rod at least Nₓ/2 iterations are needed. Moreover, smooth (long-wavelength) errors are barely affected by averaging: for a smooth function the mean of the neighbours almost coincides with the value at the node. Only “jagged” errors that change sign from node to node are damped quickly.</p><p><strong>Algorithm</strong></p><p>Given: the number of nodes Nₓ, boundary conditions, the initial guess T⁽⁰⁾, the tolerance ε and the maximum allowed number of iterations K.</p><p>Repeat for k = 0, 1, 2, …, K−1:</p><ol><li>For each interior node i = 2, …, Nₓ − 1, compute the new value from the <strong>old</strong> values of the neighbours:</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/329/1*atiGGX3t8lQyqCSJU2OU_Q.png" /></figure><p>2. Compute the new values at the boundary nodes T₁⁽ᵏ⁺¹⁾ and T_Nₓ⁽ᵏ⁺¹⁾ using the formulas for the corresponding kind of boundary condition (also from the old values of the neighbours).</p><p>3. Compute the change:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/421/1*2Edv83oxmcrw7h8wcf5Pxw.png" /></figure><p>4. If Δ⁽ᵏ⁺¹⁾ &lt; ε, stop: the answer is T⁽ᵏ⁺¹⁾. Otherwise move on to the next iteration, and the new approximation becomes the old one.</p><p>If the tolerance has not been reached within K iterations, stop and report it: the method converges too slowly or does not converge at all.</p><h3>3.3.2 Gauss–Seidel method</h3><p>The nodes are traversed from left to right, and the value of the left neighbour T_{i−1}⁽ᵏ⁺¹⁾, already computed in the current iteration, is used immediately:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/354/1*Otiyu8bAC9CVq3DCC38auA.png" /></figure><p>Memory is saved as well: a single array is enough, with values overwritten “in place”.</p><h3>3.3.3 Successive over-relaxation (SOR)</h3><p>The new Gauss–Seidel value T̃_i is “amplified” with the relaxation parameter ω:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/606/1*Vj8r3sYuMydeyzIi3LQVKQ.png" /></figure><p>With ω = 1 we get the Gauss–Seidel method, and with ω &gt; 1 over-relaxation: the correction is made larger than Gauss–Seidel suggests, “with a margin”. For a rod with conditions of the first kind the optimal value is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/396/1*PLQVDWb3JeAfMS1VNsLG9g.png" /></figure><h3>3.3.4 Stopping criterion</h3><p>Iterations are stopped when the change in the solution becomes small, or when the residual r<em>i⁽ᵏ⁾ = T</em>{i−1}⁽ᵏ⁾ − 2T<em>i⁽ᵏ⁾ + T</em>{i+1}⁽ᵏ⁾ (how far the equations are from being satisfied) becomes small:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/678/1*WQ1twhBiHg-QMlYsNXLJbw.png" /></figure><p>With slow convergence, both criteria show a value noticeably smaller than the true error. Therefore the threshold is chosen with a margin.</p><h3>3.3.5 Rate of convergence</h3><p>The Jacobi and Gauss–Seidel methods converge much more slowly than SOR, so in practice SOR or more advanced methods (conjugate gradients, multigrid) are used.</p><h3>3.3.6 Other iterative methods</h3><p>They are not needed for the one-dimensional problem: the sweep already solves it in O(Nₓ). The choice of iterative method becomes important in 2D/3D. Below, Nₓ is the number of nodes along one side.</p><ul><li><strong>Conjugate gradient method (CG)</strong> — at each iteration it chooses the correction direction and step length by itself, taking all previous steps into account, so there is no parameter like ω to tune. The number of iterations is O(Nₓ), as with SOR, but without tuning. It requires a symmetric form of the equations (see the Cholesky decomposition in section 3.2.3).</li><li><strong>Preconditioned CG (PCG)</strong> — the problem is first solved approximately by a cheap method, and CG only refines the result. Usually an incomplete Cholesky factorization, which creates no new non-zero elements, is used for this. With the modified variant (MIC), O(√Nₓ) iterations are needed. This is the workhorse for medium-sized problems.</li><li><strong>Multigrid method</strong> — a few Jacobi or Gauss–Seidel iterations quickly damp the “jagged” error, and the remaining smooth error is transferred to a grid twice as coarse. There it becomes “jagged” and is also damped quickly. The number of iterations does not depend on the grid size, and the total work is O(N), where N is the total number of nodes. This is asymptotically optimal. It is often used as a preconditioner for CG.</li><li><strong>Alternating direction implicit method (ADI)</strong> — for rectangular grids in 2D/3D: the equations are solved alternately along all rows and then along all columns, and each line is solved with the sweep (section 3.2.2). With a suitably chosen sequence of parameters, O(log Nₓ) iterations are needed.</li><li><strong>GMRES, BiCGStab</strong> — analogues of CG for non-symmetric problems (for example, with convection), usually with an ILU preconditioner.</li></ul><h3>4. Conclusion</h3><p>Let us gather the methods considered into one table:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DINTL62y_CXh96Bhgwczkw.png" /></figure><p>In the one-dimensional problem, iterative methods lose to the sweep. In the second part we will move on to the two-dimensional problem: each node will have four neighbours, the matrix will no longer be tridiagonal, the sweep will not be directly applicable, and the other direct methods will require too much memory. That is when iterative methods can become the main tool.</p><p>MATLAB code for all the methods in this article: <a href="https://github.com/Semen1996/steady-state-heat-1d">link to repository</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7d9fec900591" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>