Implicit Methods for ODEs

Compare implicit and explicit ODE solvers on a stiff problem.

// VM is the shared utility library, loaded on every page by the mathviz extension. This page uses VM.numerical.eulerSolve, VM.numerical.linearRegression, VM.expressions.makeFunction2, VM.expressions.makeNumber, VM.plotting.paddedRange, VM.ui.renderTable, VM.numerical.rk4Solve, VM.ui.applyExampleParams.
VM = window.VM

urlParams = new URLSearchParams(window.location.search)

initialN = {
  const raw = Number.parseInt(urlParams.get("n"), 10)
  return Number.isFinite(raw) ? Math.max(1, raw) : 4
}

initialMax = urlParams.get("max") ?? "80"

methodOptions = ["Reference solution", "Euler's method", "Implicit Euler"]

// Matches the line/marker colors mainPlot uses for each method's trace, so
// the overlay legend's swatches double as a color key.
// vmTheme is what makes the colors below reactive. The chart's own chrome
// (background, axes, gridlines) repaints on a dark-mode toggle by itself,
// via the relayout patch in plotly-fullscreen-button.js -- but the *trace*
// colors are values this page bakes into the traces it builds, so nothing
// repaints them unless mainPlot re-runs. Depending on vmTheme is what
// re-runs it. See VM.plotting.onThemeChange for why it fires a couple of
// frames after the toggle rather than inline.
vmTheme = Generators.observe(notify => VM.plotting.onThemeChange(notify))

chartColors = VM.plotting.colors(vmTheme)

methodColors = new Map([
  ["Reference solution", chartColors.fn],
  ["Euler's method", chartColors.alt],
  ["Implicit Euler", chartColors.ok]
])

// The page's examples and method live in method.js (the fit is the
// library's VM.numerical.orderFromErrorsVsN), so
// method.test.js can run every example and check what the convergence plot
// reports under npm test.
import {examples, methodErrors, implicitEulerSolve, endpointErrors} from "./method.js"

viewof fText = {
  const params = new URLSearchParams(window.location.search)
  const fTextInput = Inputs.text({label: "y' = f(t, y)", value: params.get("f") ?? "-5 * (y - cos(t)) - sin(t)", placeholder: "Example: -5 * y, y - t^2 + 1, y * (1 - y)"})
  fTextInput.classList.add("ojs-fill")
  fTextInput.dataset.exampleField = "f"
  return fTextInput
}

// Plot commits the current function/initial-condition/endpoint fields —
// edits above don't take effect until this is clicked, so result/mainPlot
// don't recompute on every keystroke. The n slider and the method legend
// overlaying the chart are unaffected and stay reactive.
viewof plotTrigger = {
  const plotButton = Inputs.button("Plot", {value: 0, reduce: v => v + 1})
  plotButton.classList.add("ojs-auto")
  return plotButton
}

viewof y0 = {
  const params = new URLSearchParams(window.location.search)
  const y0Input = Inputs.text({label: "Initial condition y(0)", value: params.get("y0") ?? "0", placeholder: "Example: 1, 1/2"})
  y0Input.dataset.exampleField = "y0"
  return y0Input
}

viewof bEnd = {
  const params = new URLSearchParams(window.location.search)
  const bEndInput = Inputs.text({label: "Right endpoint b", value: params.get("b") ?? "2", placeholder: "Example: 2, pi"})
  bEndInput.dataset.exampleField = "b"
  return bEndInput
}

// Always-live (not gated behind Plot) — it bounds the step slider rather
// than feeding result, so there's no reason to wait for a commit. Shares
// this row with the commit-gated fields now that a shorter label leaves
// room; see urlSyncControls below for how it stays in the URL.
viewof maxNInput = {
  const input = Inputs.text({value: initialMax, label: "Max n", placeholder: "Example: 20, 5*4"})
  input.dataset.exampleField = "max"
  return input
}

viewof exampleSelect = {
  const options = [null, ...examples]
  const select = Inputs.select(options, {label: "Try an example", format: e => e ? e.title : "Custom inputs", value: null})
  select.classList.add("ojs-fill")
  return select
}

// Plain CSS selectors, not direct viewof references -- see
// js/ui/apply-example.js's comment for why.
exampleFieldSelectors = ({
  f: '[data-example-field="f"]',
  y0: '[data-example-field="y0"]',
  b: '[data-example-field="b"]',
  max: '[data-example-field="max"]',
  n: '[data-example-field="n"]'
})

// Applies the selected example's params to the fields above and clicks
// Plot, in place — no page reload, so no scroll jump either. A plain
// "change" listener attached once to the stable native <select> (rather
// than an OJS cell reactive on exampleSelect's value) — a <select> fires
// both "input" and "change" per selection, and a reactive cell would run
// once per event, with two overlapping calls racing each other.
applyExampleFromSelect = {
  const nativeSelect = (viewof exampleSelect).querySelector("select")
  if (!nativeSelect) return
  nativeSelect.addEventListener("change", () => {
    const example = (viewof exampleSelect).value
    if (!example) return
    VM.ui.applyExampleParams(exampleFieldSelectors, example.params, viewof plotTrigger)
  })
}

// Keeps the dropdown naming the example the fields above hold ("Custom
// inputs" once none does). Reads every example field's value so it re-runs
// whenever one changes; it only sets the dropdown, never a field.
syncExampleFromFields = {
  fText; y0; bEnd; maxNInput
  VM.ui.syncExampleSelect(viewof exampleSelect, examples, exampleFieldSelectors)
}

showRefSolution = methods.includes("Reference solution")

showEuler = methods.includes("Euler's method")

showImplicitEuler = methods.includes("Implicit Euler")

// Pressing Enter in the function/initial-condition/endpoint fields clicks
// Plot instead of submitting the field's own (invisible) form. Depends
// only on the stable views, so this wiring runs once and is never
// re-attached.
enterToPlot = {
  for (const view of [viewof fText, viewof y0, viewof bEnd]) {
    const input = view.querySelector("input")
    if (!input) continue
    input.addEventListener("keydown", (e) => {
      if (e.key !== "Enter") return
      e.preventDefault()
      viewof plotTrigger.querySelector("button").click()
    })
  }
}

// committed snapshots fText/y0/bEnd only when Plot is clicked, and writes
// them back into the URL so the address bar stays a shareable link. It
// reads `viewof fText`/`viewof y0`/`viewof bEnd` (the stable DOM views)
// rather than `fText`/`y0`/`bEnd` (the reactive values), so it does NOT
// rerun on every keystroke — only when `plotTrigger` changes. It still
// runs once on initial page load, so the first render uses the
// URL-provided (or default) values with no click.
committed = {
  plotTrigger
  const math = window.math
  const fVal = (viewof fText).value
  const y0Text = (viewof y0).value
  const bText = (viewof bEnd).value
  const y0Val = VM.expressions.makeNumber(math, y0Text)
  const bVal = VM.expressions.makeNumber(math, bText)

  const params = new URLSearchParams(window.location.search)
  params.set("f", fVal)
  params.set("y0", y0Text)
  params.set("b", bText)
  history.replaceState(null, "", `${window.location.pathname}?${params}`)

  return {fText: fVal, y0: y0Val, bEnd: bVal}
}

// max is always-live rather than commit-gated, so it gets its own sync cell
// instead of piggybacking on committed above (which only runs when Plot is
// clicked).
urlSyncControls = {
  const params = new URLSearchParams(window.location.search)
  params.set("n", String(nControl))
  params.set("max", maxNInput)
  history.replaceState(null, "", `${window.location.pathname}?${params}`)
  return true
}

// result: for the current committed function/initial condition/endpoint,
// builds the endpoint-value history used by the convergence plots and
// table.
//   rows — array of { n, eulerValue, implicitEulerValue, trueValue,
//     eulerError, implicitEulerError }, one entry per subinterval count
//     n = 1..maxN — the computed y(b) for each method against a reference
//     value.
//   f — parsed right-hand side, reused for the trajectories in setup
//   trueValue — reference y(b), shared by every row
result = {
  const math = window.math

  const f = VM.expressions.makeFunction2(math, committed.fText)
  const fallback = (t, y) => NaN

  if (!f) return {rows: [], f: fallback, trueValue: NaN}

  const t0 = 0
  const y0 = committed.y0
  const b = committed.bEnd
  if (!Number.isFinite(y0) || !Number.isFinite(b) || b === t0) return {rows: [], f, trueValue: NaN}

  const {rows, trueValue} = endpointErrors(f, y0, b, maxN)
  return {rows, f, trueValue}
}

// setup computes the data needed by the main chart at the current n: each
// method's step-by-step trajectory, and a fine reference trajectory for
// the smooth "true" solution curve.
setup = {
  if (result.rows.length === 0) {
    const empty = {lo: -3, hi: 3}
    return {n: 0, eulerTs: [], eulerYs: [], implicitEulerTs: [], implicitEulerYs: [], refTs: [], refYs: [], tRange: empty, yRange: {lo: -1, hi: 1}}
  }

  const n = Math.min(Math.max(Math.round(Number(nControl)), 1), result.rows.length)

  const t0 = 0
  const y0 = committed.y0
  const b = committed.bEnd

  const euler = VM.numerical.eulerSolve(result.f, t0, y0, b, n)
  const implicitEuler = implicitEulerSolve(result.f, t0, y0, b, n)

  // A fine reference trajectory for the smooth "true" solution curve.
  const reference = VM.numerical.rk4Solve(result.f, t0, y0, b, 500)

  const tRange = VM.plotting.paddedRange([t0, b], {emptyRange: [-3, 3], relativePadding: 0.1, minPadding: 0.25})

  // The y-range fits the reference solution only, not the methods'
  // trajectories, so moving the n slider never rescales the axis — an
  // unstable explicit Euler visibly shoots off the chart instead of
  // squashing the true solution flat. Cap at 1e8 so a blowing-up reference
  // doesn't wreck the range.
  const yValues = []
  for (const y of reference.ys) if (Number.isFinite(y) && Math.abs(y) <= 1e8) yValues.push(y)
  const yRange = VM.plotting.paddedRange(yValues, {emptyRange: [-1, 1], relativePadding: 0.25, minPadding: 0.5})

  return {
    n,
    eulerTs: euler.ts, eulerYs: euler.ys,
    implicitEulerTs: implicitEuler.ts, implicitEulerYs: implicitEuler.ys,
    refTs: reference.ts, refYs: reference.ys,
    tRange, yRange
  }
}

// mainPlot draws the fine reference solution curve and, depending on the
// checkboxes, the piecewise-linear trajectory computed by each method at
// the current n.
//
// _plotDiv is kept in a closure so Plotly reuses the same DOM node across
// reactive updates — this preserves zoom and pan when n or the checkboxes
// change.
mainPlot = {
  const Plotly = window.Plotly
  let _plotDiv = null

  return (data, showRefSolution, showEuler, showImplicitEuler) => {
    const traces = []

    if (showRefSolution) {
      traces.push({x: data.refTs, y: data.refYs, type: "scatter", mode: "lines", name: "Reference solution", showlegend: false, line: {color: chartColors.fn, width: 3}})
    }

    if (showEuler && data.eulerTs.length > 0) {
      traces.push({
        x: data.eulerTs, y: data.eulerYs, type: "scatter", mode: "lines+markers", name: "Euler's method", showlegend: false,
        line: {color: chartColors.alt, width: 2}, marker: {color: chartColors.alt, size: 6}
      })
    }
    if (showImplicitEuler && data.implicitEulerTs.length > 0) {
      traces.push({
        x: data.implicitEulerTs, y: data.implicitEulerYs, type: "scatter", mode: "lines+markers", name: "Implicit Euler", showlegend: false,
        line: {color: chartColors.ok, width: 2}, marker: {color: chartColors.ok, size: 6}
      })
    }

    const layout = {
      xaxis: {title: "t", range: [data.tRange.lo, data.tRange.hi], zeroline: true},
      yaxis: {title: "y", range: [data.yRange.lo, data.yRange.hi], zeroline: true},
      hovermode: "closest",
      uirevision: "static",  // keeps zoom/pan state across reactive updates
      autosize: true
    }
    const config = VM.plotting.config()

    // First render: create the div. Later renders: update in place (preserves zoom).
    if (!_plotDiv) {
      _plotDiv = document.createElement("div")
      _plotDiv.className = "plotly-box-large"
      Plotly.newPlot(_plotDiv, traces, layout, config)
      // newPlot fires before the div is in the DOM, so Plotly measures 0 width.
      // A ResizeObserver catches the real size once it's inserted and laid out,
      // and keeps correcting it on any later layout/viewport change.
      VM.plotting.autoResize(_plotDiv)
    } else {
      Plotly.react(_plotDiv, traces, layout, config)
    }
    return _plotDiv
  }
}

// maxN parses the Max field's expression, falling back to 20 for invalid
// input so the n slider always gets a usable bound.
maxN = {
  const math = window.math
  const parsed = VM.expressions.makeNumber(math, maxNInput)
  if (parsed === null || !Number.isFinite(parsed)) return 20
  return Math.max(1, Math.round(parsed))
}

mainPlot(setup, showRefSolution, showEuler, showImplicitEuler)

viewof methods = {
  const items = []
  for (const label of methodOptions) items.push({label, color: methodColors.get(label)})
  return VM.ui.legendOverlay(items, {value: methodOptions})
}

viewof nControl = {
  const nSlider = Inputs.range([1, maxN], {step: 1, value: Math.min(initialN, maxN), label: "n (subintervals)"})
  nSlider.classList.add("ojs-fill")
  nSlider.dataset.exampleField = "n"
  return nSlider
}

// The numbers behind the chart at the current n: each shown method's value
// at the endpoint b, against the reference solution's, with its error in
// the tooltip. Always a node, never null, so Quarto never latches the cell
// as hidden.
stats = {
  const row = result.rows[setup.n - 1]
  if (!row) return VM.ui.statRow([])
  const fmt = v => Number.isFinite(v) ? String(Number(v.toPrecision(10))) : "—"
  const at = `y(${fmt(committed.bEnd)})`
  const tile = (label, value, error) => ({
    label: `${label} ${at}`, value: fmt(value),
    title: Number.isFinite(error) ? `Error ${error.toExponential(3)}` : undefined
  })
  const items = [{label: `Reference ${at}`, value: fmt(row.trueValue)}]
  if (showEuler) items.push(tile("Euler", row.eulerValue, row.eulerError))
  if (showImplicitEuler) items.push(tile("Implicit Euler", row.implicitEulerValue, row.implicitEulerError))
  return VM.ui.statRow(items)
}

Explicit (forward) Euler uses the slope at the start of the step:

\[ y_{i+1} = y_i + h\,f(t_i, y_i). \]

Implicit Euler (backward Euler) instead uses the slope at the end of the step:

\[ y_{i+1} = y_i + h\,f(t_{i+1}, y_{i+1}), \]

which requires solving for \(y_{i+1}\) at each step (this page uses a few steps of Newton’s method) — but buys stability that explicit Euler lacks.

NoteConvergence plots

// iteratesPlot draws each method's computed y(b) vs n for the entire run,
// against a reference line at the reference value of y(b) — it doesn't
// depend on the current step, so it's just plotted once per run.
iteratesPlot = {
  const eulerName = "Euler's method"
  const implicitEulerName = "Implicit Euler"
  const trueName = "Reference value"

  const marks = [
    Plot.ruleY([result.trueValue], {stroke: () => trueName, strokeDasharray: "4,3"}),
    Plot.lineY(result.rows, {x: "n", y: "eulerValue", stroke: () => eulerName}),
    Plot.dot(result.rows, {x: "n", y: "eulerValue", fill: () => eulerName, r: 3}),
    Plot.lineY(result.rows, {x: "n", y: "implicitEulerValue", stroke: () => implicitEulerName}),
    Plot.dot(result.rows, {x: "n", y: "implicitEulerValue", fill: () => implicitEulerName, r: 3})
  ]
  const colorDomain = [eulerName, implicitEulerName, trueName]
  const colorRange = [chartColors.alt, chartColors.ok, chartColors.ink]

  const chart = Plot.plot({
    width: 340, height: 300, marginLeft: 46,
    x: {label: "n"},
    y: {label: "y(b)"},
    color: {domain: colorDomain, range: colorRange},
    marks
  })
  const legend = Plot.legend({color: {domain: colorDomain, range: colorRange}})

  const container = document.createElement("div")
  container.append(chart, legend)
  return container
}
// convergencePlot draws log₁₀|error| vs log₁₀ n for both methods, with a
// linear regression line for each. The slope of each line estimates the
// order of convergence of that method (negated, since error shrinks as n
// grows) — for the entire run, so it's just plotted once per run.
//
// The fit itself (which points count, and when a method is reported
// exact) is VM.numerical.orderFromErrorsVsN.
convergencePlot = {
  const methodSpecs = [
    {name: "Euler error", color: chartColors.alt, fitColor: "#f87171"},
    {name: "Implicit Euler error", color: chartColors.ok, fitColor: "#4ade80"}
  ]

  const marks = []
  const colorDomain = []
  const colorRange = []
  // legendDomain/legendRange hold only the regression lines (and "exact"
  // entries) — the legend shown below the chart displays just the fitted
  // orders, not the raw point series, to keep it uncluttered.
  const legendDomain = []
  const legendRange = []

  for (let i = 0; i < methodSpecs.length; i++) {
    const spec = methodSpecs[i]
    const method = methodErrors[i]
    const {points, fit, order, exact, exactFromN} = VM.numerical.orderFromErrorsVsN(result.rows, result.trueValue, method.errorKey)

    marks.push(Plot.dot(points, {x: "x", y: "y", fill: () => spec.name, r: 4}))
    colorDomain.push(spec.name)
    colorRange.push(spec.color)

    let legendName = null
    if (exact) {
      legendName = `${method.name}: exact (error at rounding level)`
    } else if (fit) {
      legendName = `${method.name} order ≈ ${order.toFixed(2)}`
      marks.push(Plot.line(
        [{x: fit.xlo, y: fit.slope * fit.xlo + fit.intercept}, {x: fit.xhi, y: fit.slope * fit.xhi + fit.intercept}],
        {x: "x", y: "y", stroke: () => legendName, strokeDasharray: "6,4"}
      ))
    } else if (exactFromN !== null) {
      legendName = `${method.name}: exact from n = ${exactFromN}`
    }
    if (legendName === null) continue
    colorDomain.push(legendName)
    colorRange.push(spec.fitColor)
    legendDomain.push(legendName)
    legendRange.push(spec.fitColor)
  }

  const chart = Plot.plot({
    width: 340, height: 300, marginLeft: 46,
    x: {label: "log₁₀ n"},
    y: {label: "log₁₀ |error|"},
    color: {domain: colorDomain, range: colorRange},
    marks
  })
  const container = document.createElement("div")
  container.append(chart)
  if (legendDomain.length > 0) {
    const legend = Plot.legend({color: {domain: legendDomain, range: legendRange}})
    container.append(legend)
  }
  return container
}

NoteValue table

// Value table — shows the entire run, not just the current n, with both
// method estimates of y(b) and their errors against the reference value.
valueTable = {
  if (result.rows.length === 0) {
    // Always return a Node so Quarto's OJS runtime never latches this
    // declaration cell as hidden.
    return document.createElement("div")
  }

  const formattedRows = []
  for (const row of result.rows) {
    formattedRows.push([
      row.n,
      row.eulerValue.toPrecision(10),
      row.implicitEulerValue.toPrecision(10),
      row.trueValue.toPrecision(10),
      row.eulerError.toExponential(4),
      row.implicitEulerError.toExponential(4)
    ])
  }

  return VM.ui.renderTable({
    html,
    headers: ["n", tex`y_{\text{Euler}}(b)`, tex`y_{\text{Imp. Euler}}(b)`, tex`y_{\text{ref}}(b)`, tex`|y_{\text{Euler}} - y_{\text{ref}}|`, tex`|y_{\text{Imp. Euler}} - y_{\text{ref}}|`],
    csvHeaders: ["n", "y_Euler(b)", "y_ImplicitEuler(b)", "y_ref(b)", "|y_Euler - y_ref|", "|y_ImplicitEuler - y_ref|"],
    filename: "implicit-methods-values.csv",
    rows: formattedRows
  })
}