Dynamical Systems Method and Applications E-Book

Alexander G. Ramm

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 626

Veröffentlichungsjahr: 2013

Beschreibung

Demonstrates the application of DSM to solve a broad range of operator equations The dynamical systems method (DSM) is a powerful computational method for solving operator equations. With this book as their guide, readers will master the application of DSM to solve a variety of linear and nonlinear problems as well as ill-posed and well-posed problems. The authors offer a clear, step-by-step, systematic development of DSM that enables readers to grasp the method's underlying logic and its numerous applications. Dynamical Systems Method and Applications begins with a general introduction and then sets forth the scope of DSM in Part One. Part Two introduces the discrepancy principle, and Part Three offers examples of numerical applications of DSM to solve a broad range of problems in science and engineering. Additional featured topics include: * General nonlinear operator equations * Operators satisfying a spectral assumption * Newton-type methods without inversion of the derivative * Numerical problems arising in applications * Stable numerical differentiation * Stable solution to ill-conditioned linear algebraic systems Throughout the chapters, the authors employ the use of figures and tables to help readers grasp and apply new concepts. Numerical examples offer original theoretical results based on the solution of practical problems involving ill-conditioned linear algebraic systems, and stable differentiation of noisy data. Written by internationally recognized authorities on the topic, Dynamical Systems Method and Applications is an excellent book for courses on numerical analysis, dynamical systems, operator theory, and applied mathematics at the graduate level. The book also serves as a valuable resource for professionals in the fields of mathematics, physics, and engineering.

Leseprobe

CONTENTS

List of Figures

List of Tables

Preface

Acknowledgments

PART I

1 Introduction

1.1 What this book is about

1.2 What the DSM (Dynamical Systems Method) is

1.3 The scope of the DSM

1.4 A discussion of DSM

1.5 Motivations

2 Ill-posed problems

2.1 Basic definitions. Examples

2.2 Variational regularization

2.3 Quasi-solutions

2.4 Iterative regularization

2.5 Quasi-inversion

2.6 Dynamical systems method (DSM)

2.7 Variational regularization for nonlinear equations

3 DSM for well-posed problems

3.1 Every solvable well-posed problem can be solved by DSM

3.2 DSM and Newton-type methods

3.3 DSM and the modified Newton’s method

3.4 DSM and Gauss–Newton-type methods

3.5 DSM and the gradient method

3.6 DSM and the simple iterations method

3.7 DSM and minimization methods

3.8 Ulm’s method

4 DSM and linear ill-posed problems

4.1 Equations with bounded operators

4.2 Another approach

4.3 Equations with unbounded operators

4.4 Iterative methods

4.5 Stable calculation of values of unbounded operators

5 Some inequalities

5.1 Basic nonlinear differential inequality

5.2 An operator inequality

5.3 A nonlinear inequality

5.4 The Gronwall-type inequalities

5.5 Another operator inequality

5.6 A generalized version of the basic nonlinear inequality

5.7 Some nonlinear inequalities and applications

6 DSM for monotone operators

6.1 Auxiliary results

6.2 Formulation of the results and proofs

6.3 The case of noisy data

7 DSM for general nonlinear operator equations

7.1 Formulation of the problem. The results and proofs

7.2 Noisy data

7.3 Iterative solution

7.4 Stability of the iterative solution

8 DSM for operators satisfying a spectral assumption

8.1 Spectral assumption

8.2 Existence of a solution to a nonlinear equation

9 DSM in Banach spaces

9.1 Well-posed problems

9.2 Ill-posed problems

9.3 Singular perturbation problem

10 DSM and Newton-type methods without inversion of the derivative

10.1 Well-posed problems

10.2 Ill-posed problems

11 DSM and unbounded operators

11.1 Statement of the problem

11.2 Ill-posed problems

12 DSM and nonsmooth operators

12.1 Formulation of the results

12.2 Proofs

13 DSM as a theoretical tool

13.1 Surjectivity of nonlinear maps

13.2 When is a local homeomorphism a global one?

14 DSM and iterative methods

14.1 Introduction

14.2 Iterative solution of well-posed problems

14.3 Iterative solution of ill-posed equations with monotone operator

14.4 Iterative methods for solving nonlinear equations

14.5 Ill-posed problems

15 Numerical problems arising in applications

15.1 Stable numerical differentiation

15.2 Stable differentiation of piecewise-smooth functions

15.3 Simultaneous approximation of a function and its derivative by interpolation polynomials

15.4 Other methods of stable differentiation

15.5 DSM and stable differentiation

15.6 Stable calculating singular integrals

PART II

16 Solving linear operator equations by a Newton-type DSM

16.1 An iterative scheme for solving linear operator equations

16.2 DSM with fast decaying regularizing function

17 DSM of gradient type for solving linear operator equations

17.1 Formulations and Results

17.2 Implementation of the Discrepancy Principle

18 DSM for solving linear equations with finite-rank operators

18.1 Formulation and results

19 A discrepancy principle for equations with monotone continuous operators

19.1 Auxiliary results

19.2 A discrepancy principle

19.3 Applications

20 DSM of Newton-type for solving operator equations with minimal smoothness assumptions

20.1 DSM of Newton-type

20.2 A justification of the DSM for global homeomorphisms

20.3 DSM of Newton-type for solving nonlinear equations with monotone operators

20.4 Implicit Function Theorem and the DSM

21 DSM of gradient type

21.1 Auxiliary results

21.2 DSM gradient method

21.3 An iterative scheme

22 DSM of simple iteration type

22.1 DSM of simple iteration type

22.2 An iterative scheme for solving equations with σ-inverse monotone operators

23 DSM for solving nonlinear operator equations in Banach spaces

23.1 Proofs

23.2 The case of continuous F'(u)

PART III

24 Solving linear operator equations by the DSM

24.1 Numerical experiments with ill-conditioned linear algebraic systems

24.2 Numerical experiments with Fredholm integral equations of the first kind

24.3 Numerical experiments with an image restoration problem

24.4 Numerical experiments with Volterra integral equations of the first kind

24.5 Numerical experiments with numerical differentiation

25 Stable solutions of Hammerstein-type integral equations

25.1 DSM of Newton type

25.2 DSM of gradient type

25.3 DSM of simple iteration type

26 Inversion of the Laplace transform from the real axis using an adaptive iterative method

26.1 Introduction

26.2 Description of the method

26.3 Numerical experiments

26.4 Conclusion

Appendix A: Auxiliary results from analysis

A.1 Contraction mapping principle

A.2 Existence and uniqueness of the local solution to the Cauchy problem

A.3 Derivatives of nonlinear mappings

A.4 Implicit function theorem

A.5 An existence theorem

A.6 Continuity of solutions to operator equations with respect to a parameter

A.7 Monotone operators in Banach spaces

A.8 Existence of solutions to operator equations

A.9 Compactness of embeddings

Appendix B: Bibliographical notes

References

Index

Copyright © 2012 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.

Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representation or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print, however, may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Ramm, A. G. (Alexander G.)

Dynamical systems : methods and applications : theoretical developments and numerical examples / Alexander G. Ramm, Nguyen S. Hoang.

p. cm.

Includes bibliographical references and index.

ISBN 978-1-118-02428-7 (cloth)

1. Differentiable dynamical systems. I. Hoang, Nguyen S., 1980- II. Title.

QA614.8.R35 2011

515'.35—dc23

2011036456

10 9 8 7 6 5 4 3 2 1

To our families

LIST OF FIGURES

24.2      Plots of differences between the exact solution and solutions obtained by the DSMG, VR, and DSM.

24.3      Original and blurred noisy images.

24.4      Regularized images when noise level is 1%.

24.5      Regularized images when noise level is 5%.

26.1      Plots of numerical results for example 1.

26.2      Plots of numerical results for example 2.

26.3      Plots of numerical results for example 3.

26.4      Plots of numerical results for example 4.

26.5      Plots of numerical results for example 5.

26.6      Plots of numerical results for example 6.

26.7      Plots of numerical results for example 7.

26.8      Plots of numerical results for example 8.

26.9      Plots of numerical results for example 9.

26.10    Plots of numerical results for example 10.

26.11    Plots of numerical results for example 11.

26.12    Plots of numerical results for example 12.

LIST OF TABLES

24.1 The condition number of Hilbert matrices

26.1 Numerical results for example 1

26.2 Numerical results for example 2

26.3 Numerical results for example 3

26.4 Numerical results for example 4

26.5 Numerical results for example 5

26.6 Numerical results for example 6

26.7 Numerical results for example 7

26.8 Numerical results for example 8

26.9 Numerical results for example 9

26.10 Numerical results for example 10

26.11 Numerical results for example 11

26.12 Numerical results for example 12

26.13 Numerical results for example 13

PREFACE

In this monograph a general method for solving operator equations, especially nonlinear and ill-posed, is developed. The method is called the Dynamical Systems Method (DSM). Suppose one wants to solve an operator equation:

(0.1)

where F is a nonlinear or linear map in a Hilbert or Banach space. We assume that equation (0.1) is solvable, possibly nonuniquely. The DSM for solving equation (0.1) consists of finding a map Φ such that the Cauchy problem

(0.2)

(0.3)

If (0.3) holds, we say that DSM is justified for equation (0.1). Thus the dynamical system in this book is a synonym to an evolution problem (0.2). This explains the name DSM. The choice of the initial data u(0) will be discussed for various classes of equations (0.1). It turns out that for many classes of equations (0.1) the initial approximation u0 can be chosen arbitrarily, and, nevertheless, (0.3) holds, while for some problems the choice of u0, for which (0.3) can be established, is restricted to some neighborhood of a solution to equation (0.1).

We describe various choices of Φ in (0.2) for which it is possible to justify (0.3). It turns out that the scope of DSM is very wide. To describe it, let us introduce some notions. Let us call problem (0.1) well-posed if

(0.4)

The problem is:

(0.5)

In Part I of this book, unless otherwise stated, we assume that

(0.6)

where Mj(R) are some constants. In other words, we assume that the nonlinearity is , but the rate of its growth, as R grows, is not restricted. This assumption is dropped later on (see Chapter 20). We will obtain many results assuming only that F'(u) is continuous with respect to u.

Let us now describe briefly the scope of the DSM.

Any well-posed problem (0.1) can be solved by a DSM which converges at an exponential rate, that is,

(0.7)

where r > 0 and c1 > 0 are some constants, and F0 := F(u0).

For ill-posed problems, in general, it is not possible to estimate the rate of convergence even for linear problems; depending on the data f, this rate can be arbitrarily slow. To estimate the rate of convergence for an ill-posed problem, one has to make some additional assumptions about the data f. Remember that by “any” we mean throughout any solvable problem (0.1).

Any solvable linear equation

(0.8)

where A is a closed, linear, densely defined operator in a Hilbert space H, can be solved stably by a DSM. If noisy data fδ are given, ||fδ – f|| ≤ δ, then DSM yields a stable solution uδ for which (0.5) holds, provided that one stops at a suitable time, the “stopping time” tδ.

For linear problems (0.8) the convergence of a suitable DSM is global with respect to u0; that is, DSM converges to the unique minimal-norm solution y of (0.8) for any choice of u0.

We prove similar results for equations (0.1) with monotone operators F : H → H. Recall that F is called monotone if

(0.9)

where H is a Hilbert space and denotes the inner product in H. For hemicontinuous monotone operators the set is closed and convex, and such sets in a Hilbert space have a unique minimal-norm element. A map F is called hemicontinuous if the function is continuous with respect to λ ∈ [0, λ0) for any u,v,w ∈ H, where λ0 > 0 is a number.

DSM is justified for any solvable equation (0.1)with monotone operators with continuous F'(u), and a version of DSM is justified for continuous F without any smoothness of F assumed. Note that no restrictions on the growth of Mj(R) as R grows are imposed, so the nonlinearity is but may grow arbitrarily fast. For monotone operators we will drop assumption (0.6) and construct a convergent DSM.

We justify DSM for an arbitrary solvable equation (0.1) in a Hilbert space with nonlinearity under a very weak assumption:

(0.10)

where y is a solution to equation (0.1).

We justify DSM for operators satisfying the following spectral assumption:

(0.11)

where ε0 > 0 is an arbitrary small fixed number. Assumption (0.11) is satisfied, for example, for operators F'(u) whose regular points, that is, points z ∈ such that (F'(u) – z)–l is a bounded linear operator for

(0.12)

(0.13)

provided that (0.6) and (0.11) hold.

We discuss DSM for equations (0.1) in Banach spaces. In particular, we discuss some singular perturbation problems for equations of the type (0.13): under what conditions a solution uε to equation (0.13) converges to a solution of equation (0.1) as ε → 0.

In Newton-type methods, for example,

(0.14)

the most difficult and time-consuming part is the inversion of the derivative F'(u).

We justify a DSM method which avoids the inversion of the derivative.

For example, for well-posed problem (0.1) such a method is

(0.15)

where

(0.16)

A* is the adjoint to A operator, and u0 and Q0 are suitable initial approximations.

We also give a similar DSM scheme for solving ill-posed problem (0.1).

We justify DSM for equation (0.1) with some nonsmooth operators, for example, with monotone and hemicontinuous operators, defined on all of H.

We show that the DSM can be used as a theoretical tool for proving conditions sufficient for the surjectivity of a nonlinear map or for this map to be a global homeomorphism.

One of our motivations is to develop a general method for solving operator equations, especially nonlinear and ill-posed. The other motivation is to develop a general approach to constructing convergent iterative processes for solving these equations.

The idea of this approach is straightforward: If the DSM is justified for solving equation (0.1), that is, (0.3) holds, then one considers a discretization of (0.2), for example, the explicit Euler method:

(0.17)

and if one can prove convergence of (0.17) to the solution of (0.2), then (0.17) is a convergent iterative process for solving equation (0.1).

We prove that any solvable linear equation (0.8) (with bounded or unbounded operator A) can be solved by a convergent iterative process which converges to the unique minimal-norm solution of (0.8) for any initial approximation u0.

We prove a similar result for solvable equation (0.1) with monotone operators.

For general nonlinear equation (0.1), under suitable assumptions, a convergent iterative process is constructed. The initial approximation in this process does not have to be in a suitable neighborhood of a solution to (0.1).

We give several numerical examples of applications of the DSM. A detailed discussion of the problem of stable differentiation of noisy functions is given.

Among new technical tools, which we often use in this book, are some novel differential inequalities.

The first of these deals with the functions satisfying the following inequality:

(0.18)

where g, γ, α, and β are nonnegative functions, and γ, α, and β are continuous on [t0, ∞). We assume that there exists a positive function μ ∈ C1 [t0, ∞), such that

(0.19)

(0.20)

and prove that under the above assumptions, any nonnegative solution g(t) to (0.18) is defined on [t0, ∞) and satisfies the following inequality:

(0.21)

A more general inequality than (0.18) is also introduced, investigated, and applied. Namely,

where α(t, g) ≥ 0 is a locally Lipschitz-continuous function of g, g ≥ 0, which is continuous with respect to t for any fixed g. The assumptions on γ(t) and β(t) are as above. We prove that if

then g(t) exists for all t ≥ t0, and

Another inequality that we use is an operator version of the Gronwall inequality. Namely, assume that

(0.22)

where T(t) and G(t) are linear bounded operators on a Hilbert space depending continuously on a parameter t ∈ [0, ∞). If there exists a continuous positive function ε(t) on [0, ∞) such that

(0.23)

then the solution to (0.22) satisfies the inequality

(0.24)

This inequality shows that Q(t) is a bounded linear operator whose norm is bounded uniformly with respect to t if

(0.25)

We also study the following inequality:

(0.26)

where y(t) ≥ 0 is a continuous function on [0,∞), and . Let ω(t) ≥ 0 be a nondecreasing continuous function, . We prove that if

(0.27)

and

(0.28)

then

(0.29)

The following inequality is studied in Chapter 5:

(0.30)

where g and h are nonnegative locally integrable functions on [0, ∞), φ ≥ 0 is a continuous function on [0, ∞), and the functions and are uniformly continuous with respect to t on [0, ∞). Let ω(t) ≥ 0 be a nondecreasing continuous function . We prove that if

(0.31)

then

(0.32)

Other useful inequalities are established in Chapter 5.

The DSM is shown to be useful as a tool for proving theoretical results (see Chapter 13).

The DSM is used in Chapter 14 for construction of convergent iterative processes for solving operator equation.

In Chapter 15 some numerical problems are discussed—in particular, the problem of stable differentiation of noisy data.

We have developed a novel approach to these problems in Chapter 20.

In Part III the emphasis is on examples of numerical applications of the DSM to a number of problems of general interest. For example, the following numerical problems of practical interest are discussed: stable solution of linear ill-conditioned algebraic systems, stable solution of Fredholm and Volterra integral equations of the first kind, stable solution of Hammerstein nonlinear integral equations, image restoration by various versions of the DSM, and inversion of the Laplace transform of a compactly supported signal from a compact subset of the real axis.

The results in this book will be useful for scientists and engineers dealing with solving operator equations, linear and nonlinear, especially ill-posed, and for students in mathematics, computational mathematics, engineering, and physics.

Part I of this book is based on the monograph [151] and the book is based mostly on the papers, published by the authors and referenced in Appendix B: Bibliographical Notes. This book is essentially self-contained, and it requires a relatively modest background of the reader.

In Appendix A various auxiliary material is presented. Together with some known results, available in the literature, some less known results are included: for example, conditions for compactness of embedding operators and conditions for the continuity of the solutions to operator equations with respect to a parameter.

The table of contents gives a detailed list of topics discussed in this book.

ACKNOWLEDGMENTS

The authors thank their families for support.

This book is based mostly on the authors’s published papers and the earlier published monograph [151]. The authors thank Elsevier for permission to use this monograph.

A. G. Ramm thanks the Max Planck Institute for Mathematics in the Sciences, Leipzig, for hospitality during the Summer of 2011.

PART I

CHAPTER 1

INTRODUCTION

1.1 WHAT THIS BOOK IS ABOUT

This book is about a general method for solving operator equations

(1.1)

Here F is a nonlinear map in a Hilbert space H. Later on we consider maps F in Banach spaces as well. The general method, which we develop in this book and call the Dynamical Systems Method (DSM), consists of finding a nonlinear map ϕ(t, u) such that the Cauchy problem

(1.2)

has a unique global solution u(t), that is, the solution defined for all t ≥ 0, this solution has a limit u(∞):

(1.3)

and this limit solves equation (1.1):

(1.4)

Let us write these three conditions as

(1.5)

If (1.5) holds for the solution to (1.2), then we say that a DSM is justified for solving equation (1.1). There may be many choices of ϕ(t, u) for which DSM can be justified. A number of such choices will be given in Chapter 3 and in other chapters. It should be emphasized that we do not assume that equation (1.1) has a unique solution. Therefore the solution u(∞) depends on the initial approximation u0 in (1.2). The choice of u0 in some cases is not arbitrary and in many cases this choice is arbitrary—for example, for problems with linear operators or with nonlinear monotone operators, as well as for a wide class of general nonlinear problems (see Chapters 4, 6, 7–9, 11–12, 14).

The existence and uniqueness of the local solution to problem (1.2) is guaranteed, for example, by a Lipschitz condition imposed on ϕ:

(1.6)

where the constant L does not depend on t ∈ [0, ∞) and

is a ball, centered at the element u0 ∈ H and of radius R > 0.

1.2 WHAT THE DSM (DYNAMICAL SYSTEMS METHOD) IS

The DSM for solving equation (1.1) consists of finding a map ϕ(t, u) and an initial element u0 such that conditions (1.5) hold for the solution to the evolution problem (1.2).

If conditions (1.5) hold, then one solves Cauchy problem (1.2) and calculates the element u(∞). This element is a solution to equation (1.1). The important question one faces after finding a nonlinearity ϕ, for which (1.5) holds, is the following one: How does one solve Cauchy problem (1.2) numerically? This question has been studied much in the literature. If one uses a projection method, that is, looks for the solution of the form

(1.7)

where {fj} is an orthonormal basis of H, and J > 1 is an integer, then problem (1.2) reduces to a Cauchy problem for a system of J nonlinear ordinary differential equations for the scalar functions uj(t), 1 ≤ j ≤ J, if the right-hand side of (1.2) is projected onto the J-dimensional subspace spanned by {fj}1≤j≤J. This system is

(1.8)

Numerical solution of the Cauchy problem for systems of ordinary differential equations has been much studied in the literature.

In this book the main emphasis is on the possible choices of $ which imply properties (1.5).

1.3 THE SCOPE OF THE DSM

One of our aims is to show that DSM is applicable to a very wide variety of problems.

Specifically, we prove in this book that the DSM is applicable to the following classes of problems:

1.4 A DISCUSSION OF DSM

The reader may ask the following question:

Why would one like to solve problem (1.2) in order to solve a simpler looking problem (1.1)?

The answer is:

First, one may think that problem (1.1) is simpler than problem (1.2), but, in fact, this thinking may not be justified. Indeed, if problem (1.1) is ill-posed and nonlinear, then there is no general method for solving this problem, while one may try to solve problem (1.2) by using a projection method and solving the Cauchy problem (1.8).

Secondly, there is no clearly defined measure of the notion of the simplicity of problem (1.1) as compared with problem (1.2). As we have mentioned in Section 1.2, the numerical methods for solving (1.8) have been studied in the literature extensively (see, e.g., [39]).

The attractive features of the DSM are: its wide applicability, its flexibility [there are many choices of ϕ for which one can justify DSM, i.e., prove (1.5), and many methods for solving the Cauchy problem (1.2)], and its numerical efficiency (we show some evidences of this efficiency in Chapter 15). In particular, one can solve such classical problems as stable numerical differentiation of noisy data, solving ill-conditioned linear algebraic systems, and other problems more accurately and efficiently by a DSM than by traditional methods.

1.5 MOTIVATIONS

The motivations for the development of the DSM in this book are the following ones.

First, we want to develop a general method for solving linear and, especially, nonlinear operator equations. This method is developed especially, but not exclusively, for solving nonlinear ill-posed problems.

Secondly, we want to develop a general method for constructing convergent iterative methods for solving nonlinear ill-posed problems.

CHAPTER 2

ILL-POSED PROBLEMS

In this chapter we discuss various methods for solving ill-posed problems.

2.1 BASIC DEFINITIONS. EXAMPLES

Consider an operator equation

(2.1)

where F : X → Y is an operator from a Banach space X into a Banach space Y.

Definition 2.1.1Problem (2.1) is called well-posed (by J. Hadamard) if F is injective and surjective and has continuous inverse. If the problem is not well-posed, then it is called ill-posed.

Ill-posed problems are of great interest in applications. Let us give some examples of ill-posed problems which are of interest in applications.

Example 2.1

Solving linear algebraic systems with ill-conditioned matrices.

Let

(2.2)

(2.3)