Newton’s Method

Find a root by following tangent lines down to the x-axis.

// VM is the shared utility library, loaded on every page by the mathviz extension. This page uses VM.numerical.linearRegression, VM.expressions.makeDerivative, 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") ?? "8"

traceOptions = ["f(x)", "Tangent line", "Newton points", "Tangent x-intercepts"]

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

// Matches the line/marker colors mainPlot uses for each trace, so the
// overlay legend's swatches double as a color key. vmTheme is passed only
// to create the reactive dependency -- colors() reads the live theme itself.
chartColors = VM.plotting.colors(vmTheme)

traceColors = new Map([
  ["f(x)", chartColors.fn],
  ["Tangent line", chartColors.alt],
  ["Newton points", chartColors.alt],
  ["Tangent x-intercepts", chartColors.ok]
])

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

viewof fText = {
  const params = new URLSearchParams(window.location.search)
  const fTextInput = Inputs.text({label: "Function f(x)", value: params.get("f") ?? "x^2 - 2", placeholder: "Example: x^3 - x - 2, cos(x) - x"})
  fTextInput.classList.add("ojs-fill")
  fTextInput.dataset.exampleField = "f"
  return fTextInput
}

// 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") ?? "4", placeholder: "Example: 1.5, 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 : "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. max is listed before nothing
// here (there's no field downstream of it on this page whose view gets
// recreated), but it's kept alongside the others per the site-wide
// contract that every exampleFieldSelectors entry is a real field.
exampleFieldSelectors = ({f: '[data-example-field="f"]', 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)
  })
}

// 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; x0; maxIterationsInput
  VM.ui.syncExampleSelect(viewof exampleSelect, examples, exampleFieldSelectors)
}

// 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 fText, 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 fText/x0 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 x0` (the stable DOM views) rather than `fText`/`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 fVal = (viewof fText).value
  const x0Text = (viewof x0).value
  const x0Val = VM.expressions.makeNumber(math, x0Text)

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

  return {fText: fVal, 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
}

showFCurve = traces.includes("f(x)")

showTangent = traces.includes("Tangent line")

showNewtonPoints = traces.includes("Newton points")

showIntercepts = traces.includes("Tangent x-intercepts")

// result: runs Newton's method with the current committed inputs.
//   rows — array of { i, x, fx, dfx, xNext, error }, one entry per iteration
//   f, df — parsed functions, reused for curve sampling in setup
//   parsed — false when f(x) (or its derivative) couldn't be parsed
result = {
  const math = window.math

  // Parse f(x) and its symbolic derivative from the committed string.
  // makeFunction / makeDerivative return null if the expression is invalid.
  const f  = VM.expressions.makeFunction(math, committed.fText)
  const df = VM.expressions.makeDerivative(math, committed.fText)
  const fallback = x => NaN

  if (!f || !df) return {rows: [], f: fallback, df: fallback, parsed: false}

  return {rows: newton(f, df, committed.x0, maxIterations), f, df, parsed: true}
}

// setup computes the data shared by all three plots below: which rows are
// visible at the current step, and the axis ranges / curve samples for the
// main chart.
setup = {
  const visibleRows = result.rows.slice(0, Math.min(Number(stepControl), result.rows.length) + 1)

  // Axis ranges are computed from ALL rows, not just visibleRows,
  // so the axes stay fixed as the user steps through iterations.
  const xValues = [committed.x0]
  for (const row of result.rows) xValues.push(row.x, row.xNext)
  const xRange = VM.plotting.paddedRange(xValues, {emptyRange: [-3, 3], relativePadding: 0.25, minPadding: 0.5})

  // A wider domain (double the padding of xRange) 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 xRange.
  const xBuffer = VM.plotting.paddedRange(xValues, {emptyRange: [-6, 6], relativePadding: 0.5, minPadding: 1.0})

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

  // Collect y values for the y-axis range, including tangent line endpoints.
  // Only samples within the initial view (xRange) count, so yRange — and
  // the initial view — stay unaffected by the wider sampling.
  // Cap at 1e8 so a near-vertical tangent doesn't blow up the axis range.
  const yValues = [0]
  for (let i = 0; i < sampleXs.length; i++) {
    const x = sampleXs[i]
    if (x >= xRange.lo && x <= xRange.hi && sampleYs[i] !== null) yValues.push(sampleYs[i])
  }
  for (const row of result.rows) {
    if (Number.isFinite(row.fx) && Math.abs(row.fx) <= 1e8) yValues.push(row.fx)
    if (Number.isFinite(row.x) && Number.isFinite(row.fx) && Number.isFinite(row.dfx) && Number.isFinite(row.xNext)) {
      const tlo = Math.max(xRange.lo, Math.min(row.x, row.xNext) - 0.75)
      const thi = Math.min(xRange.hi, Math.max(row.x, row.xNext) + 0.75)
      for (const v of [row.fx + row.dfx * (tlo - row.x), row.fx + row.dfx * (thi - row.x)]) {
        if (Number.isFinite(v) && Math.abs(v) <= 1e8) yValues.push(v)
      }
    }
  }
  const yRange = VM.plotting.paddedRange(yValues, {emptyRange: [-1, 1], relativePadding: 0.25, minPadding: 0.5})

  return {visibleRows, xRange, xBuffer, yRange, sampleXs, sampleYs, parsed: result.parsed}
}

// mainPlot draws f(x), the tangent lines, the Newton points, and the
// tangent x-intercepts.
//
// _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, xRange, xBuffer, yRange, sampleXs, sampleYs, parsed}, showFCurve, showTangent, showNewtonPoints, showIntercepts) => {
    const data = []

    if (showFCurve) {
      data.push({
        x: sampleXs, y: sampleYs, type: "scatter", mode: "lines", name: "f(x)", showlegend: false,
        line: {color: chartColors.fn, width: 3},
        hovertemplate: "<b>f(x)</b><br>x = %{x:.4g}<br>f(x) = %{y:.4g}<extra></extra>"
      })
    }

    // Dotted vertical lines from the x-axis up to each Newton point
    const newtonPoints = []
    for (const r of visibleRows) {
      if (Number.isFinite(r.x) && Number.isFinite(r.fx)) newtonPoints.push(r)
    }
    if (showNewtonPoints) {
      for (const r of newtonPoints) {
        data.push({x: [r.x, r.x], y: [0, r.fx], type: "scatter", mode: "lines", showlegend: false, hoverinfo: "skip", line: {color: chartColors.muted, width: 1.5, dash: "dot"}})
      }
    }

    // Tangent lines: previous ones faded, current one solid
    const validTangentRows = []
    for (const r of visibleRows) {
      if (Number.isFinite(r.x) && Number.isFinite(r.fx) && Number.isFinite(r.dfx) && Number.isFinite(r.xNext)) {
        validTangentRows.push(r)
      }
    }
    const prevTangents = validTangentRows.slice(0, -1)
    let currentTangent = null
    if (validTangentRows.length > 0) currentTangent = validTangentRows[validTangentRows.length - 1]

    if (showTangent) {
      for (const row of prevTangents) {
        const tlo = Math.max(xRange.lo, Math.min(row.x, row.xNext) - 0.75)
        const thi = Math.min(xRange.hi, Math.max(row.x, row.xNext) + 0.75)
        data.push({
          x: [tlo, thi], y: [row.fx + row.dfx * (tlo - row.x), row.fx + row.dfx * (thi - row.x)],
          type: "scatter", mode: "lines", showlegend: false, hoverinfo: "skip",
          line: {color: VM.plotting.alpha("alt", 0.18), width: 1.5}
        })
      }
      if (currentTangent) {
        const row = currentTangent
        const tlo = Math.max(xRange.lo, Math.min(row.x, row.xNext) - 0.75)
        const thi = Math.min(xRange.hi, Math.max(row.x, row.xNext) + 0.75)
        data.push({
          x: [tlo, thi], y: [row.fx + row.dfx * (tlo - row.x), row.fx + row.dfx * (thi - row.x)],
          type: "scatter", mode: "lines", name: "Tangent line", showlegend: false,
          line: {color: chartColors.alt, width: 2.5},
          hovertemplate: "<b>Tangent line</b><br>x = %{x:.4g}<br>y = %{y:.4g}<extra></extra>"
        })
      }
    }

    // Red markers at each (x_i, f(x_i)) Newton point
    if (showNewtonPoints && newtonPoints.length > 0) {
      const xs = [], ys = [], labels = []
      for (const r of newtonPoints) {
        xs.push(r.x)
        ys.push(r.fx)
        labels.push(`x${VM.plotting.subscript(r.i)}`)
      }
      data.push({
        x: xs, y: ys,
        type: "scatter", mode: "markers+text", name: "Newton points",
        text: labels, textposition: "top center", showlegend: false,
        marker: {color: chartColors.alt, size: 10, symbol: "circle", line: {color: chartColors.halo, width: 1}},
        hovertemplate: "<b>Newton point %{text}</b><br>x = %{x:.6g}<br>f(x) = %{y:.4g}<extra></extra>"
      })
    }

    // Green markers at each tangent x-intercept (x_{i+1})
    const intercepts = []
    for (const r of visibleRows) {
      if (Number.isFinite(r.xNext)) intercepts.push({i: r.i + 1, x: r.xNext})
    }
    if (showIntercepts && intercepts.length > 0) {
      const xs = [], ys = [], labels = []
      for (const r of intercepts) {
        xs.push(r.x)
        ys.push(0)
        labels.push(`x${VM.plotting.subscript(r.i)}`)
      }
      data.push({
        x: xs, y: ys,
        type: "scatter", mode: "markers+text", name: "Tangent x-intercepts",
        text: labels, textposition: "bottom center", showlegend: false,
        marker: {color: chartColors.ok, size: 10, symbol: "circle", line: {color: chartColors.halo, width: 1}},
        hovertemplate: "<b>Tangent x-intercept %{text}</b><br>x = %{x:.6g}<extra></extra>"
      })
    }

    // An unparseable f(x) makes result.rows empty and every sample NaN, so
    // without this the chart would just draw an empty grid -- visually
    // identical to a valid function that happens to plot nothing. Keyed on
    // the parse itself, not on the samples: a valid f whose iterates run off
    // to ~1e8 has every sample capped to null, and that isn't a bad formula.

    const layout = {
      // margin is intentionally not set here: VM.plotting.layout's shared
      // margins plus automargin give the axis titles and tick labels room,
      // which a flat {l:0,r:0,t:0,b:0} took away.
      xaxis: {title: "x", range: [xRange.lo, xRange.hi], zeroline: true},
      yaxis: {title: "f(x)", range: [yRange.lo, yRange.hi], zeroline: true},
      annotations: parsed ? [] : VM.plotting.emptyState("Couldn't read that function — check the formula for f(x)."),
      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)
      // 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, 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, showFCurve, showTangent, showNewtonPoints, showIntercepts)

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
}

// The numbers behind the current step: the tangent's x-intercept xₙ₊₁ (the
// root estimate), f there, and the step from xₙ. Always a node, never null,
// so Quarto never latches the cell as hidden.
stats = {
  const rows = setup.visibleRows
  if (rows.length === 0) return VM.ui.statRow([])
  const row = rows[rows.length - 1]
  const n = VM.plotting.subscript(row.i)
  const n1 = VM.plotting.subscript(row.i + 1)
  const fmt = v => Number.isFinite(v) ? String(Number(v.toPrecision(10))) : "—"
  const fNext = Number.isFinite(row.xNext) ? result.f(row.xNext) : NaN
  return VM.ui.statRow([
    {label: `Root estimate x${n1}`, value: fmt(row.xNext)},
    {label: `f(x${n1})`, value: Number.isFinite(fNext) ? fNext.toExponential(3) : "—"},
    {label: `|x${n1} − x${n}|`, value: Number.isFinite(row.error) ? row.error.toExponential(3) : "—"}
  ])
}

Newton’s method finds roots of \(f(x)=0\) by repeatedly linearizing: from \(x_n\), it follows the tangent line at \((x_n, f(x_n))\) to its \(x\)-intercept,

\[ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}. \]

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₁₀|eₙ₊₁| vs log₁₀|eₙ| (successive step sizes,
// eₙ = |xₙ₊₁ − xₙ|) with a linear regression line, for the entire run.
// Newton converges quadratically for a simple root (eₙ₊₁ ~ C·eₙ²), which
// isn't a straight line vs n or log(n) — it only takes a handful of steps
// to hit machine precision, and fitting log|error| vs n (as bisection and
// fixed-point iteration do, since they converge linearly) gives a "slope"
// that's just an artifact of however many points survive before underflow.
// This log-log successive-error plot is the standard diagnostic instead:
// its slope estimates the order of convergence p directly (≈2 for a simple
// root, ≈1 for a multiple root, as in the default x² example).
convergencePlot = {
  const {points: logRows, fit} = VM.numerical.orderFromSuccessiveErrors(result.rows, "error", "xNext")

  const pointsName = "log₁₀|eₙ₊₁| vs log₁₀|eₙ|"
  const marks = [Plot.dot(logRows, {x: "x", 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 order, not the raw
  // point series, to keep it uncluttered.
  const legendDomain = [], legendRange = []

  if (fit) {
    const lineName = `order ≈ ${fit.slope.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: () => 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: "log₁₀|eₙ|"},
    y: {label: "log₁₀|eₙ₊₁|"},
    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 like "A two-cycle failure", where too few
  // finite successive-error points survive to fit).
  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 fxCell = "NaN"
    if (Number.isFinite(row.fx)) fxCell = row.fx.toExponential(5)

    let dfxCell = "NaN"
    if (Number.isFinite(row.dfx)) dfxCell = row.dfx.toExponential(5)

    let xNextCell = "NaN"
    if (Number.isFinite(row.xNext)) xNextCell = row.xNext.toPrecision(10)

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

    formattedRows.push([row.i, xCell, fxCell, dfxCell, xNextCell, errorCell])
  }

  return VM.ui.renderTable({
    html,
    headers: ["n", tex`x_n`, tex`f(x_n)`, tex`f'(x_n)`, tex`x_{n+1}`, tex`|x_{n+1} - x_n|`],
    csvHeaders: ["n", "x_n", "f(x_n)", "f'(x_n)", "x_{n+1}", "|x_{n+1} - x_n|"],
    filename: "newton-method-iterations.csv",
    rows: formattedRows
  })
}