Skip to content

Initial Value Problems and Pattern Recognition

CSIR NET geophysics: Euler, Heun and Runge-Kutta for IVPs, stability and stiffness, plus pattern recognition: features, k-NN, k-means and confusion matrices.

  • 19 min read
  • Updated
On this page · 13 sections
  1. Prerequisites
  2. The Hook: One Station, Two Problems
  3. Initial Value Problems
  4. One-Step Methods
  5. Stability and Stiffness
  6. Pattern Recognition
  7. Memory Tricks
  8. Don’t Confuse
  9. Common Mistakes
  10. Practice
  11. Quick Revision Table
  12. Key Takeaways
  13. What’s Next

Prerequisites

The Hook: One Station, Two Problems

Initial Value Problems

An initial value problem (IVP) is

$$y' = f(t, y), \qquad y(t_0) = y_0,$$

where \( y \) may be a vector. If \( f \) is continuous and Lipschitz in \( y \) (\( \lVert f(t, y_1) - f(t, y_2) \rVert \le L\lVert y_1 - y_2 \rVert \)), a unique solution exists near \( t_0 \) (Picard–Lindelöf).

Higher-order equations become systems

Every \( n \)th-order ODE becomes \( n \) first-order ones. The seismometer equation for mass displacement \( x \) relative to the frame, with natural angular frequency \( \omega_0 \), damping ratio \( \zeta \) and ground acceleration \( a_g(t) \), is

$$x'' + 2\zeta\omega_0 x' + \omega_0^2 x = -a_g(t).$$

Set \( y_1 = x \), \( y_2 = x' \):

$$y_1' = y_2, \qquad y_2' = -a_g(t) - 2\zeta\omega_0 y_2 - \omega_0^2 y_1.$$

Every method below now applies component by component.

Where IVPs show up in geophysics

ProblemThe IVP
Instrument responsedamped oscillator driven by ground motion
Seismic ray tracingray equations in arc length, from source position and take-off angle
Radioactive decay chainscoupled linear ODEs \( N_i' = \lambda_{i-1}N_{i-1} - \lambda_i N_i \)
Thermal history of a cooling body (lumped model)\( T' = -k(T - T_{\text{ambient}}) \)
Two-point problems by shootingguess the missing initial value (e.g. take-off angle), integrate, adjust until the ray hits the receiver

The shooting method is worth noting: a boundary value problem is turned into a sequence of initial value problems plus a root-finding step on the unknown initial condition.

One-Step Methods

Grid \( t_n = t_0 + nh \), \( y_n \approx y(t_n) \).

MethodFormulaLocal errorGlobal error (order)\( f \) evaluations per step
Euler (explicit)\( y_{n+1} = y_n + hf(t_n, y_n) \)\( O(h^2) \)\( O(h) \), order 11
Heun (modified Euler, RK2)\( k_1 = f(t_n, y_n) \), \( k_2 = f(t_n + h, y_n + hk_1) \), \( y_{n+1} = y_n + \frac{h}{2}(k_1 + k_2) \)\( O(h^3) \)order 22
Midpoint (RK2)\( y_{n+1} = y_n + hf\!\left(t_n + \frac{h}{2}, y_n + \frac{h}{2}k_1\right) \)\( O(h^3) \)order 22
Classical RK4\( y_{n+1} = y_n + \frac{h}{6}(k_1 + 2k_2 + 2k_3 + k_4) \)\( O(h^5) \)order 44
Backward (implicit) Euler\( y_{n+1} = y_n + hf(t_{n+1}, y_{n+1}) \)\( O(h^2) \)order 1solve an equation each step

For RK4:

$$k_1 = f(t_n, y_n),\quad k_2 = f\!\left(t_n + \tfrac{h}{2}, y_n + \tfrac{h}{2}k_1\right),\quad k_3 = f\!\left(t_n + \tfrac{h}{2}, y_n + \tfrac{h}{2}k_2\right),\quad k_4 = f(t_n + h, y_n + hk_3).$$

The weights \( 1, 2, 2, 1 \) over 6 are Simpson’s rule, with the midpoint slope sampled twice.

How error scales

With global order \( p \), halving \( h \) divides the global error by \( 2^p \): by 2 for Euler, 4 for Heun, 16 for RK4. The local (one-step) error is one power higher, but about \( \frac{t - t_0}{h} \) steps accumulate, which takes one power back.

Adaptive step size. Embedded Runge–Kutta pairs (for example Runge–Kutta–Fehlberg 4(5)) compute two estimates of different order from shared stages. Their difference estimates the local error, and the code shrinks \( h \) where the solution changes quickly and enlarges it where it is smooth.

Multistep methods (brief)

Multistep methods reuse earlier values instead of extra stages:

  • Adams–Bashforth (explicit), two-step: \( y_{n+1} = y_n + \frac{h}{2}\left(3f_n - f_{n-1}\right) \), order 2.
  • Adams–Moulton (implicit) formulas are more accurate and more stable.
  • Predictor–corrector: predict with Adams–Bashforth, correct with Adams–Moulton. One new \( f \) evaluation per step per correction, against four for RK4.
  • They are not self-starting: the first few values come from a one-step method such as RK4.

Stability and Stiffness

Apply a method to the test equation \( y' = \lambda y \) with \( \operatorname{Re}\lambda < 0 \) (a decaying solution). Each step multiplies \( y \) by an amplification factor \( R(z) \), \( z = h\lambda \). The method is stable when \( \lvert R(z) \rvert \le 1 \).

Method\( R(z) \)Real-axis stability interval
Euler\( 1 + z \)\( -2 \le z \le 0 \), so \( h \le \frac{2}{\lvert\lambda\rvert} \)
Heun / RK2\( 1 + z + \frac{z^2}{2} \)\( -2 \le z \le 0 \)
RK4\( 1 + z + \frac{z^2}{2} + \frac{z^3}{6} + \frac{z^4}{24} \)about \( -2.79 \le z \le 0 \)
Backward Euler\( \frac{1}{1 - z} \)the whole left half-plane (A-stable)

Stiffness. A system is stiff when it contains widely different time scales, for example \( \lambda_1 = -1 \) and \( \lambda_2 = -1000 \). The fast component dies out almost at once, yet an explicit method must keep \( h < \frac{2}{1000} = 0.002 \) for the whole run to stay stable. Implicit methods (backward Euler, trapezoidal/Crank–Nicolson, backward differentiation formulas) remove this restriction at the cost of solving an equation each step. Chemical kinetics, coupled heat and fluid flow and some decay chains are stiff.

Pattern Recognition

Pattern recognition assigns an object, described by measurements, to one of several classes. Geophysics uses it wherever there are too many records for a person to label by hand.

Vocabulary

  • Pattern / feature vector \( \mathbf{x} = (x_1, \dots, x_d) \): the measurements describing one object (for a depth sample in a well: gamma ray, bulk density, neutron porosity, resistivity).
  • Feature space: the \( d \)-dimensional space in which each object is a point.
  • Class \( \omega_k \): a category (sand, shale, carbonate; earthquake, explosion, noise).
  • Classifier / decision rule: maps \( \mathbf{x} \) to a class. The surfaces separating classes are decision boundaries.
graph LR
    A["Raw data (traces, logs, images)"] --> B["Pre-processing (filter, normalise)"]
    B --> C["Feature extraction / selection (PCA)"]
    C --> D["Classifier (trained on labelled data)"]
    D --> E["Class label"]
    E --> F["Evaluation (confusion matrix, cross-validation)"]

Supervised versus unsupervised

Supervised (classification)Unsupervised (clustering)
Training datalabelled examplesno labels
Outputone of the predefined classesgroups discovered in the data
Methodsminimum-distance, k-nearest neighbours, Bayes / discriminant analysis, perceptron and neural networks, support vector machinesk-means, hierarchical clustering (dendrograms), self-organising maps
Well-log examplelogs at cored depths labelled with lithology; predict the rest of the wellgroup log responses into “electrofacies”, then interpret them

Distance and similarity

Most simple classifiers need a distance between a pattern and a class.

  • Euclidean: \( d^2 = \sum_i (x_i - \mu_i)^2 \). It treats all features alike, so features in large units dominate.
  • Standardise first: \( z_i = \frac{x_i - \bar{x}_i}{s_i} \). Density in g/cm³ (range about 0.5) and gamma ray in API units (range of the order of 100) are otherwise on wildly different scales.
  • Mahalanobis: \( d^2 = (\mathbf{x} - \boldsymbol{\mu})^{\mathsf T}\Sigma^{-1}(\mathbf{x} - \boldsymbol{\mu}) \). It scales by each class’s spread and accounts for correlation between features. With uncorrelated features it reduces to \( \sum_i \frac{(x_i - \mu_i)^2}{\sigma_i^2} \).

Supervised classifiers

  1. Minimum-distance (nearest mean): assign \( \mathbf{x} \) to the class whose mean is closest. Decision boundaries are perpendicular bisectors between means (with Euclidean distance).
  2. k-nearest neighbours (k-NN): find the \( k \) training points nearest to \( \mathbf{x} \) and take a majority vote. No training phase, but every prediction searches the whole training set. Small \( k \) follows noise; large \( k \) blurs boundaries.
  3. Bayes classifier: choose the class with the largest posterior \( P(\omega_k \mid \mathbf{x}) \propto p(\mathbf{x} \mid \omega_k)P(\omega_k) \). It minimises the probability of misclassification when the densities are known. With Gaussian classes sharing one covariance matrix, the boundaries are linear (linear discriminant analysis); with different covariances, quadratic.
  4. Perceptron and artificial neural networks: a single perceptron draws one linear boundary and converges only if the classes are linearly separable. Multilayer networks trained by back-propagation draw non-linear boundaries.
  5. Support vector machines: place the linear boundary with the maximum margin between classes; kernels give non-linear boundaries.

Unsupervised: k-means

  1. Choose \( k \) and initial centroids.
  2. Assign each point to its nearest centroid.
  3. Update each centroid to the mean of its points.
  4. Repeat 2 and 3 until assignments stop changing.

Each pass cannot increase the within-cluster sum of squared distances, so the algorithm converges, but to a local minimum that depends on the starting centroids. Run it from several starts.

Measuring performance

A confusion matrix tabulates true class against predicted class on test data the classifier has not seen.

Predicted sandPredicted shale
True sand (60)546
True shale (40)832
  • Accuracy = correct / total = \( \frac{54 + 32}{100} = 0.86 \).
  • Recall (sensitivity) for sand = \( \frac{54}{60} = 0.90 \): the fraction of true sands found.
  • Precision for sand = \( \frac{54}{54 + 8} = \frac{54}{62} \approx 0.87 \): the fraction of “sand” calls that are right.

Overfitting: a classifier that is perfect on its training data but poor on new data has memorised noise. Guard against it with a separate test set or k-fold cross-validation, and keep the number of features modest relative to the number of training samples.

Geophysical applications

ApplicationFeaturesTypical method
Lithology / electrofacies from well logsgamma ray, density, neutron, sonic, resistivityk-means or hierarchical clustering; supervised with core labels
Seismic facies mappingamplitude, frequency, continuity attributesself-organising maps, neural networks
Earthquake versus explosion discriminationbody-wave versus surface-wave magnitude, spectral ratios, depthlinear discriminant (explosions are shallow and relatively weak in surface waves for a given body-wave magnitude)
Automatic event detectionratio of short-term to long-term average amplitude (STA/LTA)threshold trigger, then a classifier
First-break and phase pickingwaveform windowsneural networks

Memory Tricks

Don’t Confuse

ThisvsThat
Local truncation error \( O(h^{p+1}) \)Global error \( O(h^p) \)
Explicit Euler: \( f \) at the old point, conditionally stableImplicit Euler: \( f \) at the new point, A-stable
One-step (Runge–Kutta): self-startingMultistep (Adams): needs starting values
Instability (blow-up, method property)Stiffness (problem property: widely separated time scales)
Classification: labels knownClustering: labels unknown
k-NN: \( k \) = number of neighbours votingk-means: \( k \) = number of clusters
Euclidean distance: ignores spread and correlationMahalanobis distance: scaled by the covariance
Precision: \( \frac{TP}{TP + FP} \)Recall: \( \frac{TP}{TP + FN} \)

Common Mistakes

Practice

All questions below are original practice questions written for this page. They are not from any CSIR NET paper.

Level 1: Foundation

  1. What is the global order of the classical Runge–Kutta method?
  2. For \( y' = \lambda y \) with real \( \lambda < 0 \), what is the largest step for which explicit Euler is stable?
  3. Is k-means a supervised or an unsupervised method?
Answers
  1. Fourth order (global error \( O(h^4) \), local \( O(h^5) \)).
  2. \( h = \frac{2}{\lvert\lambda\rvert} \), from \( \lvert 1 + h\lambda \rvert \le 1 \).
  3. Unsupervised. It needs no class labels.

Level 2: Part B Style

Practice Q1. For \( y' = t + y \), \( y(0) = 1 \), one step of Heun’s (modified Euler) method with \( h = 0.1 \) gives \( y(0.1) \approx \):

(a) 1.100 (b) 1.105 (c) 1.110 (d) 1.115

Answer: (c) 1.110

\( k_1 = f(0, 1) = 0 + 1 = 1 \). Predictor \( y = 1 + 0.1(1) = 1.1 \). \( k_2 = f(0.1, 1.1) = 0.1 + 1.1 = 1.2 \).

\( y_1 = 1 + \frac{0.1}{2}(1 + 1.2) = 1 + 0.11 = 1.110 \).

Check against the exact solution \( y = 2e^t - t - 1 \): \( y(0.1) = 2(1.1051709) - 1.1 = 1.1103418 \), so the error is \( 3.4 \times 10^{-4} \). Option (a) is the Euler value.

Practice Q2. A decay chain contains a component with \( \lambda = -50 \) per year. For explicit Euler to remain stable, the time step must not exceed:

(a) 0.02 yr (b) 0.04 yr (c) 0.1 yr (d) 2 yr

Answer: (b) 0.04 yr

\( h \le \frac{2}{\lvert\lambda\rvert} = \frac{2}{50} = 0.04 \) yr. Option (a) is \( \frac{1}{\lvert\lambda\rvert} \), the limit for a non-oscillating (monotone) Euler solution, not for stability.

Practice Q3. An RK4 solution has a global error of \( 8 \times 10^{-6} \) at \( t = 1 \) with \( h = 0.1 \). With \( h = 0.05 \) the error is expected to be about:

(a) \( 4 \times 10^{-6} \) (b) \( 2 \times 10^{-6} \) (c) \( 5 \times 10^{-7} \) (d) \( 2.5 \times 10^{-7} \)

Answer: (c) 5 × 10⁻⁷

Global error \( \propto h^4 \): halving \( h \) divides it by 16. \( \frac{8 \times 10^{-6}}{16} = 5 \times 10^{-7} \). Option (d) uses the local-error power \( h^5 \) (division by 32).

Practice Q4. A lithology classifier tested on 100 samples gives the confusion matrix in the table on this page (54 sand correctly found, 6 sand called shale, 8 shale called sand, 32 shale correctly found). The precision for the class “sand” is about:

(a) 0.80 (b) 0.86 (c) 0.87 (d) 0.90

Answer: (c) 0.87

Precision = true positives / all predicted positives = \( \frac{54}{54 + 8} = \frac{54}{62} = 0.871 \).

(b) is the overall accuracy \( \frac{86}{100} \); (d) is the recall \( \frac{54}{60} \).

Level 3: Part C Style

Practice Q5. Two well-log classes are modelled with uncorrelated features. Class A has mean (0, 0) and standard deviation 1 in each feature; class B has mean (4, 0) and standard deviation 3 in each feature. A new sample is at (1.6, 0). Which statement is correct?

(a) It is assigned to A by both Euclidean and Mahalanobis distance. (b) It is assigned to B by both. (c) It is assigned to A by Euclidean distance and to B by Mahalanobis distance. (d) It is assigned to B by Euclidean distance and to A by Mahalanobis distance.

Answer: (c)

Euclidean: to A, \( 1.6 \); to B, \( \lvert 1.6 - 4 \rvert = 2.4 \). Nearer A.

Mahalanobis (uncorrelated, so divide each difference by that class’s standard deviation): to A, \( \frac{1.6}{1} = 1.6 \); to B, \( \frac{2.4}{3} = 0.8 \). Nearer B.

The wide spread of class B makes a point 2.4 units away less unusual for B than a point 1.6 units away is for A. This is exactly what Euclidean distance ignores.

Practice Q6. k-means with \( k = 2 \) is run on the values 2, 4, 5, 11, 12, 14 starting from centroids 2 and 4. At convergence the centroids are:

(a) 2 and 9.2 (b) 3 and 12 (c) \( \frac{11}{3} \) and \( \frac{37}{3} \) (d) 4.5 and 12.5

Answer: (c) 11/3 and 37/3

Pass 1: clusters {2} and {4, 5, 11, 12, 14}; centroids 2 and 9.2 (option a is this intermediate state).

Pass 2: 4 (distances 2 and 5.2) and 5 (distances 3 and 4.2) move to the first cluster. Clusters {2, 4, 5} and {11, 12, 14}; centroids \( \frac{11}{3} \approx 3.67 \) and \( \frac{37}{3} \approx 12.33 \).

Pass 3: no point changes cluster (5 is 1.33 from 3.67 and 7.33 from 12.33). Converged.

Practice Q7. Consider these statements:

  1. The classical RK4 method needs four evaluations of \( f \) per step and has global error \( O(h^4) \).
  2. Backward Euler is A-stable, so its solution is accurate for any step size.
  3. For a stiff system, explicit methods are limited by the fastest decaying mode even after it has died out.
  4. A single-layer perceptron can classify any two classes perfectly, given enough training.

Which are correct?

(a) 1 and 3 only (b) 1, 2 and 3 only (c) 2 and 4 only (d) 1, 3 and 4 only

Answer: (a) 1 and 3 only
  1. True.
  2. False. A-stability means no blow-up for decaying problems at any step size; accuracy is still first order and poor for large \( h \).
  3. True. That is the definition of the stiffness difficulty.
  4. False. A single perceptron draws one linear boundary; it fails for classes that are not linearly separable (the XOR arrangement is the standard counter-example).

Quick Revision Table

IdeaFormula or fact
Euler\( y_{n+1} = y_n + hf_n \); order 1
Heun (modified Euler)\( y_{n+1} = y_n + \frac{h}{2}[f(t_n, y_n) + f(t_{n+1}, y_n + hf_n)] \); order 2
RK4\( \frac{h}{6}(k_1 + 2k_2 + 2k_3 + k_4) \); order 4; 4 evaluations
Error scalinghalve \( h \): global error ÷ \( 2^p \)
Euler stability\( \lvert 1 + h\lambda \rvert \le 1 \); real \( \lambda \): \( h \le 2/\lvert\lambda\rvert \)
RK4 real stability limitabout \( h\lvert\lambda\rvert \le 2.79 \)
Stiff systemsuse implicit methods (backward Euler, BDF, trapezoidal)
Higher-order ODErewrite as a first-order system
Supervised / unsupervisedlabels known / groups found
Mahalanobis\( (\mathbf{x} - \boldsymbol\mu)^{\mathsf T}\Sigma^{-1}(\mathbf{x} - \boldsymbol\mu) \)
k-meansassign to nearest centroid, update means, repeat; local minimum
Accuracy, precision, recall\( \frac{TP + TN}{N} \), \( \frac{TP}{TP + FP} \), \( \frac{TP}{TP + FN} \)

Key Takeaways

What’s Next