Fixed Point Iteration

Solves x = g(x) by repeatedly applying g, and shows when that iteration converges or diverges.

// VM is the shared utility library, loaded globally via _includes/head-scripts.html (js/**). This page uses VM.numerical.linearRegression, VM.expressions.makeFunction, VM.expressions.makeNumber, VM.plotting.paddedRange, VM.ui.renderTable, VM.ui.applyExampleParams.
VM = window.VM

urlParams = new URLSearchParams(window.location.search)

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

traceOptions = ["g(x)", "y = x", "Cobweb path", "Iterates"]

// Matches the line/marker colors mainPlot uses for each 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)

traceColors = new Map([
  ["g(x)", chartColors.fn],
  ["y = x", chartColors.ink],
  ["Cobweb path", chartColors.alt],
  ["Iterates", chartColors.ok]
])

// examples backs the "Try an example" dropdown near the top controls.
examples = [
  {
    title: "Classic convergent iteration",
    params: {max: "20", g: "cos(x)", x0: "1"}
  },
  {
    title: "Converges to the positive fixed point",
    params: {max: "20", g: "sqrt(x + 2)", x0: "1"}
  },
  {
    title: "Chaotic wandering",
    params: {max: "20", g: "2*cos(x)", x0: "1"}
  },
  {
    title: "Repelling fixed point",
    params: {max: "20", g: "2*x", x0: "0.1"}
  },
  {
    title: "Divergent oscillation",
    params: {max: "20", g: "1 - 2*x", x0: "0.2"}
  },
  {
    title: "Neutral two-cycle",
    params: {max: "20", g: "1 - x", x0: "0.2"}
  },
  {
    title: "Very slow convergence",
    params: {max: "20", g: "x - x^3", x0: "0.2"}
  }
]

viewof gText = {
  const params = new URLSearchParams(window.location.search)
  const gTextInput = Inputs.text({label: "Function g(x)", value: params.get("g") ?? "cos(x)", placeholder: "Example: cos(x), sqrt(x + 2), exp(-x)"})
  gTextInput.classList.add("ojs-fill")
  gTextInput.dataset.exampleField = "g"
  return gTextInput
}

// Plot commits the current function/x₀ fields — edits above don't take
// effect until this is clicked, so result/mainPlot don't recompute on
// every keystroke. The step slider overlaid on the plot is unaffected and stays reactive.
viewof plotTrigger = {
  const plotButton = Inputs.button("Plot", {value: 0, reduce: v => v + 1})
  plotButton.classList.add("ojs-auto")
  return plotButton
}

viewof x0 = {
  const params = new URLSearchParams(window.location.search)
  const x0Input = Inputs.text({label: "Initial guess x₀", value: params.get("x0") ?? "1", placeholder: "Example: 1, pi/4"})
  x0Input.dataset.exampleField = "x0"
  return x0Input
}

// 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 maxIterationsInput = {
  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 : "Pick an example…", 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 = ({g: '[data-example-field="g"]', x0: '[data-example-field="x0"]', max: '[data-example-field="max"]'})

// 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)
  })
}

// Pressing Enter in the function/x₀ 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 gText, viewof x0]) {
    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 gText/x0 only when Plot is clicked, and writes them
// back into the URL so the address bar stays a shareable link. It reads
// `viewof gText`/`viewof x0` (the stable DOM views) rather than `gText`/`x0`
// (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 gVal = (viewof gText).value
  const x0Text = (viewof x0).value
  const x0Val = VM.expressions.makeNumber(math, x0Text)

  const params = new URLSearchParams(window.location.search)
  params.set("g", gVal)
  params.set("x0", x0Text)
  history.replaceState(null, "", `${window.location.pathname}?${params}`)

  return {gText: gVal, x0: x0Val}
}

// 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("max", maxIterationsInput)
  history.replaceState(null, "", `${window.location.pathname}?${params}`)
  return true
}

showGCurve = traces.includes("g(x)")

showDiagonal = traces.includes("y = x")

showCobweb = traces.includes("Cobweb path")

showIterates = traces.includes("Iterates")

// result: runs fixed-point iteration with the current committed inputs.
//   rows — array of { i, x, gx, error }, one entry per iteration
//   g    — parsed function, reused for curve sampling in setup
result = {
  const math = window.math

  const g        = VM.expressions.makeFunction(math, committed.gText)
  const fallback = x => NaN

  if (!g) return {rows: [], g: fallback}

  const rows  = []
  const initialGuess = committed.x0

  if (!Number.isFinite(initialGuess)) return {rows: [], g}

  let x = initialGuess
  let i = 0
  while (i < maxIterations) {
    const gx = g(x)

    // Stop if g(x) blows up — the iteration has diverged.
    if (!Number.isFinite(gx)) {
      rows.push({i, x, gx, error: NaN})
      return {rows, g}
    }

    const error = Math.abs(gx - x)
    rows.push({i, x, gx, error})

    x = gx
    i++
  }
  return {rows, g}
}

// setup computes the data shared by all three plots below: which rows are
// visible at the current step, the axis range for the cobweb diagram
// (square, since it plots y = x), and the sampled curve for g(x).
setup = {
  const visibleRows = result.rows.slice(0, Math.min(Number(stepControl), result.rows.length) + 1)

  // Axis ranges from ALL rows so the axes stay fixed while stepping.
  // The cobweb diagram uses a square plot (same range for x and y).
  const rangeValues = [committed.x0]
  for (const row of result.rows) rangeValues.push(row.x, row.gx)
  const range = VM.plotting.paddedRange(rangeValues, {emptyRange: [-2, 2], relativePadding: 0.25, minPadding: 0.5})

  // A wider domain (double the padding of range) so the curve is already
  // sampled beyond the initial view — panning/zooming out reveals more of
  // the curve instead of blank canvas. The initial view stays range.
  const bufferRange = VM.plotting.paddedRange(rangeValues, {emptyRange: [-4, 4], relativePadding: 0.5, minPadding: 1.0})

  // Sample g across the buffer range for the smooth curve trace.
  const sampleCount = 500
  const sampleXs = Array.from({length: sampleCount}, (_, i) => bufferRange.lo + (bufferRange.hi - bufferRange.lo) * i / (sampleCount - 1))
  const sampleYs = []
  for (const x of sampleXs) {
    const y = result.g(x)
    if (Number.isFinite(y)) {
      sampleYs.push(y)
    } else {
      sampleYs.push(null)
    }
  }

  return {visibleRows, range, bufferRange, sampleXs, sampleYs, x0: committed.x0}
}

// mainPlot draws the cobweb diagram: g(x), the diagonal y = x, and the
// staircase path of iterates.
//
// _plotDiv is kept in a closure so Plotly reuses the same DOM node across
// reactive updates — this preserves zoom and pan when the step changes.
mainPlot = {
  const Plotly = window.Plotly
  let _plotDiv = null

  return ({visibleRows, range, bufferRange, sampleXs, sampleYs, x0}, showGCurve, showDiagonal, showCobweb, showIterates) => {
    const data = []

    if (showGCurve) {
      // The iteration function g(x)
      data.push({x: sampleXs, y: sampleYs, type: "scatter", mode: "lines", name: "g(x)", showlegend: false, line: {color: chartColors.fn, width: 3}})
    }
    if (showDiagonal) {
      // The diagonal y = x — fixed points lie where g(x) crosses this line.
      // Spans the buffer so it's still visible when the user pans/zooms out.
      data.push({x: [bufferRange.lo, bufferRange.hi], y: [bufferRange.lo, bufferRange.hi], type: "scatter", mode: "lines", name: "y = x", showlegend: false, line: {color: chartColors.ink, width: 2, dash: "dash"}})
    }
    // The x-axis reference
    data.push({x: [bufferRange.lo, bufferRange.hi], y: [0, 0], type: "scatter", mode: "lines", showlegend: false, line: {color: chartColors.muted, width: 1}})

    if (visibleRows.length > 0) {
      // Build the cobweb staircase path.
      // From x_i on the diagonal, go vertically to (x_i, g(x_i)) on the curve,
      // then horizontally to (g(x_i), g(x_i)) on the diagonal.
      const cobwebX = []
      const cobwebY = []
      if (Number.isFinite(x0)) { cobwebX.push(x0); cobwebY.push(x0) }
      for (const row of visibleRows) {
        if (!Number.isFinite(row.x) || !Number.isFinite(row.gx)) continue
        cobwebX.push(row.x,  row.gx)
        cobwebY.push(row.gx, row.gx)
      }

      // Green dots marking each iterate x_i on the diagonal
      const iterateXs = [], iterateLabels = []
      for (const r of visibleRows) {
        if (Number.isFinite(r.x)) {
          iterateXs.push(r.x)
          iterateLabels.push(`x_${r.i}`)
        }
      }

      if (showCobweb) {
        // The staircase path
        data.push({x: cobwebX, y: cobwebY, type: "scatter", mode: "lines+markers", name: "Cobweb path", showlegend: false,
          line: {color: chartColors.alt, width: 2}, marker: {color: chartColors.alt, size: 7}})
      }
      if (showIterates) {
        data.push({
          x: iterateXs,
          y: iterateXs,
          type: "scatter", mode: "markers+text", name: "Iterates", showlegend: false,
          text: iterateLabels,
          textposition: "top center",
          marker: {color: chartColors.ok, size: 9, symbol: "circle", line: {color: chartColors.halo, width: 1}}
        })
      }
    }

    const layout = {
      xaxis: {title: "x", range: [range.lo, range.hi], zeroline: true},
      yaxis: {title: "y", range: [range.lo, range.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, data, layout, config)
      VM.plotting.autoResize(_plotDiv)
    } else {
      Plotly.react(_plotDiv, data, layout, config)
    }
    return _plotDiv
  }
}

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

mainPlot(setup, showGCurve, showDiagonal, showCobweb, showIterates)

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

viewof stepControl = {
  const stepSlider = Inputs.range([0, maxIterations - 1], {step: 1, value: 0, label: "n"})
  stepSlider.classList.add("ojs-fill")
  return stepSlider
}

NoteConvergence plots

// iteratesPlot draws xₙ vs n for the entire run — it doesn't depend on the
// current step, so it's just plotted once per run.
iteratesPlot = {
  const xAccessor = row => {
    if (Number.isFinite(row.x)) return row.x
    return null
  }
  return Plot.plot({
    width: 340, height: 300, marginLeft: 46,
    x: {label: "n"},
    y: {label: "xₙ"},
    marks: [
      Plot.lineY(result.rows, {x: "i", y: xAccessor, stroke: chartColors.fn}),
      Plot.dot(result.rows, {x: "i", y: xAccessor, fill: chartColors.fn, r: 4})
    ]
  })
}
// convergencePlot draws log₁₀|xₙ − g(xₙ)| vs n (semi-log) with a linear
// regression line, for the entire run — it doesn't depend on the current
// step, so it's just plotted once per run.
convergencePlot = {
  const logRows = []
  for (const r of result.rows) {
    if (Number.isFinite(r.error) && r.error > 0) {
      logRows.push({n: r.i, y: Math.log10(r.error)})
    }
  }

  const pointsName = "log₁₀|xₙ − g(xₙ)|"
  const marks = [Plot.dot(logRows, {x: "n", y: "y", fill: () => pointsName, r: 4})]
  const colorDomain = [pointsName], colorRange = [chartColors.alt]
  // legendDomain/legendRange hold only the regression line(s) — the legend
  // shown below the chart displays just the fitted slope, not the raw
  // point series, to keep it uncluttered.
  const legendDomain = [], legendRange = []

  const regressionPoints = []
  for (const row of logRows) regressionPoints.push({x: row.n, y: row.y})
  const fit = VM.numerical.linearRegression(regressionPoints)
  if (fit) {
    const lineName = `slope ≈ ${fit.slope.toFixed(2)}`
    marks.push(Plot.line(
      [{n: fit.xlo, y: fit.slope * fit.xlo + fit.intercept}, {n: fit.xhi, y: fit.slope * fit.xhi + fit.intercept}],
      {x: "n", y: "y", stroke: () => lineName, strokeDasharray: "6,4"}
    ))
    colorDomain.push(lineName)
    colorRange.push(chartColors.accent2)
    legendDomain.push(lineName)
    legendRange.push(chartColors.accent2)
  }

  const chart = Plot.plot({
    width: 340, height: 300, marginLeft: 46,
    x: {label: "n"},
    y: {label: "log₁₀|xₙ − g(xₙ)|"},
    color: {domain: colorDomain, range: colorRange},
    marks
  })

  const container = document.createElement("div")
  container.append(chart)
  // Plot.legend throws on an empty domain/range — there's no legend to
  // show when the run didn't produce a regression line (e.g. a
  // non-converging example).
  if (legendDomain.length > 0) {
    const legend = Plot.legend({color: {domain: legendDomain, range: legendRange}})
    container.append(legend)
  }
  return container
}

NoteIteration table

// Iteration table — shows the entire run, not just the current step.
iterationTable = {
  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) {
    let xCell = "NaN"
    if (Number.isFinite(row.x)) xCell = row.x.toPrecision(10)

    let gxCell = "NaN"
    if (Number.isFinite(row.gx)) gxCell = row.gx.toPrecision(10)

    let errorCell = "NaN"
    if (Number.isFinite(row.error)) errorCell = row.error.toExponential(4)

    formattedRows.push([row.i, xCell, gxCell, errorCell])
  }

  return VM.ui.renderTable({
    html,
    headers: ["n", "x_n", tex`g(x_n) = x_{n+1}`, tex`|x_{n+1} - x_n|`],
    csvHeaders: ["n", "x_n", "g(x_n) = x_{n+1}", "|x_{n+1} - x_n|"],
    filename: "fixed-point-iterations.csv",
    rows: formattedRows
  })
}

Fixed point iteration solves \(x=g(x)\) by repeatedly applying \(g\): \(x_{n+1}=g(x_n)\). If the sequence converges to a value \(\alpha\), then \(\alpha=g(\alpha)\) — a fixed point of \(g\).