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
On this page · 13 sections
Prerequisites
- Numerical Differentiation, Integration, FDM and FEM: one-step ODE methods are quadrature rules in disguise, and the stability ideas carry over.
- The full mathematical treatment (Picard iteration, order proofs) is in Picard, Euler, Modified Euler and Runge-Kutta in Mathematical Sciences.
- For the pattern-recognition half: means, variances and covariance matrices, and principal component analysis (see Linear Models, Regression and Multivariate Analysis).
- Chapter map: Numerical Analysis and Inversion.
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
| Problem | The IVP |
|---|---|
| Instrument response | damped oscillator driven by ground motion |
| Seismic ray tracing | ray equations in arc length, from source position and take-off angle |
| Radioactive decay chains | coupled 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 shooting | guess 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) \).
| Method | Formula | Local error | Global error (order) | \( f \) evaluations per step |
|---|---|---|---|---|
| Euler (explicit) | \( y_{n+1} = y_n + hf(t_n, y_n) \) | \( O(h^2) \) | \( O(h) \), order 1 | 1 |
| 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 2 | 2 |
| 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 2 | 2 |
| Classical RK4 | \( y_{n+1} = y_n + \frac{h}{6}(k_1 + 2k_2 + 2k_3 + k_4) \) | \( O(h^5) \) | order 4 | 4 |
| Backward (implicit) Euler | \( y_{n+1} = y_n + hf(t_{n+1}, y_{n+1}) \) | \( O(h^2) \) | order 1 | solve 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 data | labelled examples | no labels |
| Output | one of the predefined classes | groups discovered in the data |
| Methods | minimum-distance, k-nearest neighbours, Bayes / discriminant analysis, perceptron and neural networks, support vector machines | k-means, hierarchical clustering (dendrograms), self-organising maps |
| Well-log example | logs at cored depths labelled with lithology; predict the rest of the well | group 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
- Minimum-distance (nearest mean): assign \( \mathbf{x} \) to the class whose mean is closest. Decision boundaries are perpendicular bisectors between means (with Euclidean distance).
- 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.
- 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.
- 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.
- Support vector machines: place the linear boundary with the maximum margin between classes; kernels give non-linear boundaries.
Unsupervised: k-means
- Choose \( k \) and initial centroids.
- Assign each point to its nearest centroid.
- Update each centroid to the mean of its points.
- 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 sand | Predicted shale | |
|---|---|---|
| True sand (60) | 54 | 6 |
| True shale (40) | 8 | 32 |
- 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
| Application | Features | Typical method |
|---|---|---|
| Lithology / electrofacies from well logs | gamma ray, density, neutron, sonic, resistivity | k-means or hierarchical clustering; supervised with core labels |
| Seismic facies mapping | amplitude, frequency, continuity attributes | self-organising maps, neural networks |
| Earthquake versus explosion discrimination | body-wave versus surface-wave magnitude, spectral ratios, depth | linear discriminant (explosions are shallow and relatively weak in surface waves for a given body-wave magnitude) |
| Automatic event detection | ratio of short-term to long-term average amplitude (STA/LTA) | threshold trigger, then a classifier |
| First-break and phase picking | waveform windows | neural networks |
Memory Tricks
Don’t Confuse
| This | vs | That |
|---|---|---|
| Local truncation error \( O(h^{p+1}) \) | Global error \( O(h^p) \) | |
| Explicit Euler: \( f \) at the old point, conditionally stable | Implicit Euler: \( f \) at the new point, A-stable | |
| One-step (Runge–Kutta): self-starting | Multistep (Adams): needs starting values | |
| Instability (blow-up, method property) | Stiffness (problem property: widely separated time scales) | |
| Classification: labels known | Clustering: labels unknown | |
| k-NN: \( k \) = number of neighbours voting | k-means: \( k \) = number of clusters | |
| Euclidean distance: ignores spread and correlation | Mahalanobis 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
- What is the global order of the classical Runge–Kutta method?
- For \( y' = \lambda y \) with real \( \lambda < 0 \), what is the largest step for which explicit Euler is stable?
- Is k-means a supervised or an unsupervised method?
Answers
- Fourth order (global error \( O(h^4) \), local \( O(h^5) \)).
- \( h = \frac{2}{\lvert\lambda\rvert} \), from \( \lvert 1 + h\lambda \rvert \le 1 \).
- 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:
- The classical RK4 method needs four evaluations of \( f \) per step and has global error \( O(h^4) \).
- Backward Euler is A-stable, so its solution is accurate for any step size.
- For a stiff system, explicit methods are limited by the fastest decaying mode even after it has died out.
- 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
- True.
- False. A-stability means no blow-up for decaying problems at any step size; accuracy is still first order and poor for large \( h \).
- True. That is the definition of the stiffness difficulty.
- 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
| Idea | Formula 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 scaling | halve \( 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 limit | about \( h\lvert\lambda\rvert \le 2.79 \) |
| Stiff systems | use implicit methods (backward Euler, BDF, trapezoidal) |
| Higher-order ODE | rewrite as a first-order system |
| Supervised / unsupervised | labels known / groups found |
| Mahalanobis | \( (\mathbf{x} - \boldsymbol\mu)^{\mathsf T}\Sigma^{-1}(\mathbf{x} - \boldsymbol\mu) \) |
| k-means | assign 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
- Well- and Ill-Posed Problems and Least Squares: turning data back into a model, and why that is harder than forward modelling.
- Gradient and Direct Search, Generalized Inversion, SVD and Global Optimization.
- Numerical Analysis and Inversion: Quick Revision.
- Related unit: Signal Processing, where STA/LTA triggers and filtering prepare the traces that classifiers use.