Quadratic convergence of Newton's method for convex interpolation and smoothing
type: Item
instance of: scholarly article
title: Quadratic convergence of Newton's method for convex interpolation and smoothing
zbMATH Open document ID: 1014.65011
author: Liqun Qi
author: A. L. Dontchev
author: Houduo Qi
published in: Constructive Approximation
publication date: 2003-03-17T00:00:00Z
review text: The paper is concerned with the convergence of Newton's method for solving the convex interpolation problem: (1) minimize \(\|f''\|_2\) subject to \(f(t_i) = y_i\), \(i=1,2,\dots , N+2\), with \(f\in W^{2.2}\) convex on \([a,b]\), where \(a=t_1<t_2<\dots <t_{N+2}=b,\) and \(y_i\) are given. One supposes that the divided differences \(d_i\) at \((t_i,y_i)\) are all strictly positive. In a previous paper [Numer. Math. 87, No. 3, 435-456 (2001; Zbl 0970.65009)] the authors have shown that problem (1) has a unique solution which is a cubic spline. It turns out that problem (1) is equivalent to its Lagrange dual: \[ \max_{\lambda\in \mathbb R^N}\left[-\frac{1}{2}\int_a^b\left(\sum_{i=1}^N \lambda _iB_i(t)\right)_+^2 dt + \sum_{i=1}^N\lambda _id_i\right], \] where \(B_i\) are the normalized cubic spline. In the second section of the paper the authors study the analytic properties of the function \(F\) given by \[ F_k(\lambda) = \int_a^b\left(\sum_{i=1}^N \lambda _iB_i(t)\right)_+ ^2B_i(t) dt. \] Since the function \(F\) is Lipschitz, by Rademacher's theorem it is differentiable a.e., and the study is carried out via Bouligand's generalized Jacobian. A damped Newton method, having global quadratic convergence, is also presented. Similar results are obtained also for the convex smoothing method. The paper ends with some numerical examples.
Mathematics Subject Classification ID: 65D05
Mathematics Subject Classification ID: 65D10
Mathematics Subject Classification ID: 41A29
Mathematics Subject Classification ID: 41A05
zbMATH DE Number: 1883401
zbMATH Keywords: Newton's method
zbMATH Keywords: best convex interpolation
zbMATH Keywords: convex smoothing
zbMATH Keywords: splines
zbMATH Keywords: quadratic convergence
zbMATH Keywords: numerical examples
reviewed by: Stefan Cobzaş
MaRDI profile type: Publication
full work available at URL: s00365-002-0513-2
OpenAlex ID: W1491846897
DOI: 10.1007/S00365-002-0513-2
Recommended article: Constrained interpolation and smoothing
Recommended article: Q3596516
Recommended article: Q4426068
Recommended article: Finite termination of a dual Newton method for convex best \(C^1\) interpolation and smoothing
Recommended article: Q3808606
Recommended article: Convergence of Newton's method for convex best interpolation
Recommended article: Regularity and well-posedness of a dual program for convex best \(C^{1}\)-spline interpolation
Recommended article: Convex interval interpolation with cubic splines. II
Recommended article: An unconstrained dual program for computing convex \(C^ 1\)-spline approximants
Recommended article: Convex interval interpolation with cubic splines
description: scientific article; zbMATH DE number 1883401