Fixed Point Iteration

// 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 = window.VM

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")
  return gTextInput
}

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"})
  return x0Input
}

// 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 below 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 stepControl = {
  const stepSlider = Inputs.range([0, maxIterations - 1], {step: 1, value: 0, label: "Step"})
  stepSlider.classList.add("ojs-fill")
  return stepSlider
}

viewof maxIterationsInput = {
  const input = Inputs.text({value: "20", label: "Max", placeholder: "Example: 20, 5*4"})
  input.classList.add("ojs-auto")
  return input
}

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

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

// 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}) => {
    const data = [
      // The iteration function g(x)
      {x: sampleXs, y: sampleYs, type: "scatter", mode: "lines", name: "g(x)", showlegend: true, line: {color: "#2563eb", width: 3}},
      // 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.
      {x: [bufferRange.lo, bufferRange.hi], y: [bufferRange.lo, bufferRange.hi], type: "scatter", mode: "lines", name: "y = x", showlegend: true, line: {color: "#111827", width: 2, dash: "dash"}},
      // The x-axis reference
      {x: [bufferRange.lo, bufferRange.hi], y: [0, 0], type: "scatter", mode: "lines", showlegend: false, line: {color: "#94a3b8", 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}`)
        }
      }

      data.push(
        // The staircase path
        {x: cobwebX, y: cobwebY, type: "scatter", mode: "lines+markers", name: "Cobweb path", showlegend: true,
          line: {color: "#dc2626", width: 2}, marker: {color: "#dc2626", size: 7}},
        {
          x: iterateXs,
          y: iterateXs,
          type: "scatter", mode: "markers+text", name: "Iterates", showlegend: true,
          text: iterateLabels,
          textposition: "top center",
          marker: {color: "#16a34a", size: 9, symbol: "circle", line: {color: "white", width: 1}}
        }
      )
    }

    const layout = {
      margin: {l: 0, r: 0, t: 0, b: 0},
      xaxis: {title: "x", range: [range.lo, range.hi], zeroline: true},
      yaxis: {title: "y", range: [range.lo, range.hi], zeroline: true, zerolinecolor: "#94a3b8", gridcolor: "#e2e8f0", linecolor: "#cbd5e1"},
      legend: {orientation: "h", y: -0.08},
      hovermode: "closest",
      uirevision: "static",  // keeps zoom/pan state across reactive updates
      autosize: true
    }
    const config = {responsive: true, displaylogo: false}

    // 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)
      new ResizeObserver(() => Plotly.Plots.resize(_plotDiv)).observe(_plotDiv)
    } else {
      Plotly.react(_plotDiv, data, layout, config)
    }
    return _plotDiv
  }
}

mainPlot(setup)

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: "#2563eb"}),
      Plot.dot(result.rows, {x: "i", y: xAccessor, fill: "#2563eb", 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 = ["#dc2626"]
  // 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("#9333ea")
    legendDomain.push(lineName)
    legendRange.push("#9333ea")
  }

  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 legend = Plot.legend({color: {domain: legendDomain, range: legendRange}})

  const container = document.createElement("div")
  container.append(chart, 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\).

Examples

Fixed point iteration can behave very differently depending on the function \(g\) and the starting point \(x_0\). The examples below illustrate attraction, repulsion, oscillation, slow convergence, and divergence.

Click any example to load it into the app.

Classic convergent iteration

g(x) = cos(x),   x₀ = 1

The iteration xₙ₊₁ = cos(xₙ) converges to the Dottie number, the fixed point of cosine.

Converges to the positive fixed point

g(x) = √(x + 2),   x₀ = 1

This converges to x = 2, solving x = √(x + 2). The cobweb path moves steadily toward the intersection with y = x.

Babylonian iteration for √2

g(x) = (x + 2/x)/2,   x₀ = 1

A very effective fixed point iteration for computing √2. It converges much faster than many ordinary fixed point schemes.

Gentle attraction

g(x) = 1 + 0.5 sin(x),   x₀ = 0

The slope near the fixed point has magnitude less than 1, so the fixed point is attractive and the iteration settles down.

Oscillatory convergence

g(x) = 2 cos(x),   x₀ = 1

The iterates approach the fixed point while bouncing from one side to the other. The cobweb diagram shows a visible zig-zag pattern.

Slow attraction

g(x) = 1.2x − 0.2x²,   x₀ = 0.2

The fixed point at x = 1 is attractive, but convergence can be slow when the slope is close to 1 in magnitude.

Repelling fixed point

g(x) = 2x,   x₀ = 0.1

Although x = 0 is a fixed point, the slope has magnitude greater than 1, so nearby iterates are pushed away.

Divergent oscillation

g(x) = 1 − 2x,   x₀ = 0.2

The iteration alternates across the fixed point with growing amplitude because the slope has magnitude greater than 1.

Neutral two-cycle

g(x) = 1 − x,   x₀ = 0.2

The sequence jumps back and forth between two values. The fixed point exists at x = 0.5, but the iteration does not approach it.

Very slow convergence

g(x) = x − x³,   x₀ = 0.2

The fixed point x = 0 is attracting, but g′(0) = 1, so convergence is much slower than linear.